Mitochondrial respiratory complex subunits assemble in supercomplexes. Studies of supercomplexes have typically relied upon antibody-based quantification, often limited to a single subunit per respiratory complex. To provide a deeper insight into mitochondrial and supercomplex plasticity, we combine native electrophoresis and mass spectrometry to determine the supercomplexome of skeletal muscle from sedentary and exercise-trained mice. We quantify 422 mitochondrial proteins within 10 supercomplex bands in which we show the debated presence of complexes II and V. Exercise-induced mitochondrial biogenesis results in non-stoichiometric changes in subunits and incorporation into supercomplexes. We uncover the dynamics of supercomplex-related assembly proteins and mtDNA-encoded subunits after exercise. Furthermore, exercise affects the complexing of Lactb, an obesity-associated mitochondrial protein, and ubiquinone biosynthesis proteins. Knockdown of ubiquinone biosynthesis proteins leads to alterations in mitochondrial respiration. Our approach can be applied to broad biological systems. In this instance, comprehensively analyzing respiratory supercomplexes illuminates previously undetectable complexity in mitochondrial plasticity.