The genes in the Myb superfamily encode for three related transcription factors in most vertebrates, A-, B-, and c-Myb, with functionally distinct roles, whereas most invertebrates have a single Myb. B-Myb plays an essential role in cell division and cell cycle progression, c-Myb is involved in hematopoiesis, and A-Myb is involved in spermatogenesis and regulating expression of pachytene PIWI interacting RNAs, a class of small RNAs involved in posttranscriptional gene regulation and the maintenance of reproductive tissues. Comparisons between teleost fish and tetrapods suggest that the emergence and functional divergence of the Myb genes were linked to the two rounds of whole-genome duplication early in vertebrate evolution. We combined phylogenetic, synteny, structural, and gene expression analyses of the Myb paralogs from elephant shark and lampreys with data from 12 bony vertebrates to reconstruct the early evolution of vertebrate Mybs. Phylogenetic and synteny analyses suggest that the elephant shark and Japanese lamprey have copies of the A-, B-, and c-Myb genes, implying their origin could be traced back to the common ancestor of lampreys and gnathostomes. However, structural and gene expression analyses suggest that their functional roles diverged between gnathostomes and cyclostomes. In particular, we did not detect A-Myb expression in testis suggesting that the involvement of A-Myb in the pachytene PIWI interacting RNA pathway is probably a gnathostome-specific innovation. We speculate that the secondary loss of a central domain in lamprey A-Myb underlies the functional differences between the cyclostome and gnathostome A-Myb proteins.