Mitochondrial fission involves preconstriction of the organelle followed by scission by dynamin-related protein Drp1. Preconstriction is facilitated by actin and nonmuscle myosin II through a mechanism that remains unclear, mostly, due to unknown cytoskeleton ultrastructure at mitochondrial constrictions. Here, using platinum replica electron microscopy, we show that mitochondria in cells are embedded into an interstitial cytoskeletal network containing abundant unbranched actin filaments. Both spontaneous and induced mitochondrial constrictions typically associate with a criss-cross array of long actin filaments that comprise a part of this interstitial network. Nonmuscle myosin II is found adjacent to mitochondria without specific enrichments at the constriction sites. During ionomycin-induced mitochondrial fission, F-actin clouds colocalize with mitochondrial constriction sites, whereas myosin II clouds mostly fluctuate nearby. We propose that myosin II promotes mitochondrial constriction by inducing stochastic deformations of the interstitial actin network, which applies pressure onto mitochondrial surface, thus initiating curvature-sensing mechanisms that complete mitochondrial constriction.