Mitochondrial fission involves the preconstriction of an organelle followed by scission by dynamin-related protein Drp1. Preconstriction is facilitated by actin and non-muscle myosin II through a mechanism that remains unclear, largely due to the unknown cytoskeletal ultrastructure at mitochondrial constrictions. Here, using platinum replica electron microscopy, we show that mitochondria in cells are embedded in an interstitial cytoskeletal network that contains abundant unbranched actin filaments. Both spontaneous and induced mitochondrial constrictions typically associate with a criss-cross array of long actin filaments that comprise part of this interstitial network. Non-muscle myosin II is found adjacent to mitochondria but is not specifically enriched at the constriction sites. During ionomycin-induced mitochondrial fission, F-actin clouds colocalize with mitochondrial constriction sites, whereas dynamic myosin II clouds are present in the vicinity of constrictions. We propose that myosin II promotes mitochondrial constriction by inducing stochastic deformations of the interstitial actin network, which applies pressure on the mitochondrial surface and thus initiates curvature-sensing mechanisms that complete mitochondrial constriction.