All vertebrate nervous systems, except those of agnathans, make extensive use of the myelinated fiber, a structure formed by coordinated interplay between neuronal axons and glial cells. Myelinated fibers, by enhancing the speed and efficiency of nerve cell communication allowed gnathostomes to evolve extensively, forming a broad range of diverse lifestyles in most habitable environments. The axon-covering myelin sheaths are structurally and biochemically novel as they contain high portions of lipid and a few prominent low molecular weight proteins often considered unique to myelin. Here we searched genome and EST databases to identify orthologs and paralogs of the following myelin-related proteins: (1) myelin basic protein (MBP), (2) myelin protein zero (MPZ, formerly P0), (3) proteolipid protein (PLP1, formerly PLP), (4) peripheral myelin protein-2 (PMP2, formerly P2), (5) peripheral myelin protein-22 (PMP22) and (6) stathmin-1 (STMN1). Although widely distributed in gnathostome/vertebrate genomes, neither MBP nor MPZ are present in any of nine invertebrate genomes examined. PLP1, which replaced MPZ in tetrapod CNS myelin sheaths, includes a novel ‘tetrapod-specific’ exon (see also Möbius et al., 2009). Like PLP1, PMP2 first appears in tetrapods and like PLP1 its origins can be traced to invertebrate paralogs. PMP22, with origins in agnathans, and STMN1 with origins in protostomes, existed well before the evolution of gnathostomes. The coordinated appearance of MBP and MPZ with myelin sheaths and of PLP1 with tetrapod CNS myelin suggests interdependence – new proteins giving rise to novel vertebrate structures.