The protein composition of myelin in the central nervous system (CNS) has changed at the evolutionary transition from fish to tetrapods, when a lipid-associated transmembrane-tetraspan (proteolipid protein, PLP) replaced an adhesion protein of the immunoglobulin superfamily (P0) as the most abundant constituent. Here, we review major steps of proteolipid evolution. Three paralog proteolipids (PLP/DM20/DMalpha, M6B/DMgamma and the neuronal glycoprotein M6A/DMbeta) exist in vertebrates from cartilaginous fish to mammals, and one (M6/CG7540) can be traced in invertebrate bilaterians including the planktonic copepod Calanus finmarchicus that possess a functional myelin equivalent. In fish, DMalpha and DMgamma are coexpressed in oligodendrocytes but are not major myelin components. PLP emerged at the root of tetrapods by the acquisition of an enlarged cytoplasmic loop in the evolutionary older DMalpha/DM20. Transgenic experiments in mice suggest that this loop enhances the incorporation of PLP into myelin. The evolutionary recruitment of PLP as the major myelin protein provided oligodendrocytes with the competence to support long-term axonal integrity. We suggest that the molecular shift from P0 to PLP also correlates with the concentration of adhesive forces at the radial component, and that the new balance between membrane adhesion and dynamics was favorable for CNS myelination.