All extant vertebrates possess an adaptive immune system wherein diverse immune receptors are created and deployed in specialized blood cell lineages. Recent advances in DNA sequencing and developmental resources for basal vertebrates have facilitated numerous comparative analyses that have shed new light on the molecular and cellular bases of immune defense and the mechanisms of immune receptor diversification in the "jawless" vertebrates. With data from these key species in hand, it is becoming possible to infer some general aspects of the early evolution of vertebrate adaptive immunity. All jawed vertebrates assemble their antigen-receptor genes through combinatorial recombination of different "diversity" segments into immunoglobulin or T-cell receptor genes. However, the jawless vertebrates employ an analogous, but independently derived set of immune receptors in order to recognize and bind antigens: the variable lymphocyte receptors (VLRs). The means by which this locus generates receptor diversity and achieves antigen specificity is of considerable interest because these mechanisms represent a completely independent strategy for building a large immune repertoire. Therefore, studies of the VLR system are providing insight into the fundamental principles and evolutionary potential of adaptive immune recognition systems. Here we review and synthesize the wealth of data that have been generated towards understanding the evolution of the adaptive immune system in the jawless vertebrates.