Capturing mitochondria’s intricate and dynamic structure poses a daunting challenge for optical nanoscopy. Different labeling strategies have been demonstrated for live-cell stimulated emission depletion (STED) microscopy of mitochondria, but orthogonal strategies are yet to be established, and image acquisition has suffered either from photodamage to the organelles or from rapid photobleaching. Therefore, live-cell nanoscopy of mitochondria has been largely restricted to 2D single-color recordings of cancer cells. Here, by conjugation of cyclooctatetraene to a benzo-fused cyanine dye, we report a mitochondrial inner-membrane (IM) fluorescent marker, PK Mito Orange (PKMO), featuring efficient STED at 775 nm, strong photostability and markedly reduced phototoxicity. PKMO enables super-resolution recordings of inner-membrane dynamics for extended periods in immortalized mammalian cell lines, primary cells, and organoids. Photostability and reduced phototoxicity of PKMO open the door to live-cell 3D STED nanoscopy of mitochondria for three-dimensional analysis of the convoluted IM. PKMO is optically orthogonal with green and far-red markers allowing multiplexed recordings of mitochondria using commercial STED microscopes. Using multi-color STED, we demonstrate that imaging with PKMO can capture the sub-mitochondrial localization of proteins, or interactions of mitochondria with different cellular components, such as the ER or the cytoskeleton at sub-100 nm resolution. Thereby, this work offers a versatile tool for studying mitochondrial inner-membrane architecture and dynamics in a multiplexed manner.