Blue-native gel electrophoresis (BN) is a powerful method for protein separation. Combined with liquid chromatography-tandem mass spectrometry (LC-MS/MS) it enables large-scale identification of protein complexes and their subunits. Current BN-MS approaches, however, are limited in size resolution, comprehensiveness and quantification. Here, we present a new methodology combining defined sub-mm slicing of BN gels by a cryo-microtome with high-performance LC-MS/MS and label-free quantification of proteins. Application of this cryo-slicing BN-MS approach (csBN-MS) to mitochondria from brain demonstrated a high degree of comprehensiveness, quantification accuracy and size resolution. The technique provided abundance-mass profiles for 743 mitochondrial proteins including all canonical subunits of the oxidative respiratory chain assembled into 13 distinct (super)complexes. Moreover, the data revealed COX7R as a constitutive subunit of distinct supercomplexes and identified novel assemblies of porins and TOM proteins. Together, csBN-MS enables quantitative profiling of complexomes with resolution close to the limits of native gel electrophoresis.