Hagfish and lampreys are the only living representatives of the jawless vertebrates (agnathans), and compared with jawed vertebrates (gnathostomes), they provide insight into the embryology, genomics, and body plan of the ancestral vertebrate. However, this insight has been obscured by controversy over their interrelationships. Morphological cladistic analyses have identified lampreys and gnathostomes as closest relatives, whereas molecular phylogenetic studies recover a monophyletic Cyclostomata (hagfish and lampreys as closest relatives). Here, we show through deep sequencing of small RNA libraries, coupled with genomic surveys, that Cyclostomata is monophyletic: hagfish and lampreys share 4 unique microRNA families, 15 unique paralogues of more primitive microRNA families, and 22 unique substitutions to the mature gene products. Reanalysis of morphological data reveals that support for cyclostome paraphyly was based largely on incorrect character coding, and a revised dataset is not decisive on the mono- vs. paraphyly of cyclostomes. Furthermore, we show fundamental conservation of microRNA expression patterns among lamprey, hagfish, and gnathostome organs, implying that the role of microRNAs within specific organs is coincident with their appearance within the genome and is conserved through time. Together, these data support the monophyly of cyclostomes and suggest that the last common ancestor of all living vertebrates was a more complex organism than conventionally accepted by comparative morphologists and developmental biologists.