The complexes mediating oxidative phosphorylation (OXPHOS) in the inner mitochondrial membrane consist of proteins encoded in the nuclear or the mitochondrial DNA. The mitochondrially encoded membrane proteins (mito-MPs) represent the catalytic core of these complexes and follow complicated pathways for biogenesis. Owing to their overall hydrophobicity, mito-MPs are co-translationally inserted into the inner membrane by the Oxa1 insertase. After insertion, OXPHOS biogenesis factors mediate the assembly of mito-MPs into complexes and participate in the regulation of mitochondrial translation, while protein quality control factors recognize and degrade faulty or excess proteins. This review summarizes the current understanding of these early steps occurring during the assembly of mito-MPs by concentrating on results obtained in the model organism baker's yeast.