Although jawless vertebrates are apparently capable of adaptive immune responses, they have not been found to possess the recombinatorial antigen receptors shared by all jawed vertebrates. Our search for the phylogenetic roots of adaptive immunity in the lamprey has instead identified a new type of variable lymphocyte receptors (VLRs) composed of highly diverse leucine-rich repeats (LRR) sandwiched between amino- and carboxy-terminal LRRs. An invariant stalk region tethers the VLRs to the cell surface by means of a glycosyl-phosphatidyl-inositol anchor. To generate rearranged VLR genes of the diversity necessary for an anticipatory immune system, the single lamprey VLR locus contains a large bank of diverse LRR cassettes, available for insertion into an incomplete germline VLR gene. Individual lymphocytes express a uniquely rearranged VLR gene in monoallelic fashion. Different evolutionary strategies were thus used to generate highly diverse lymphocyte receptors through rearrangement of LRR modules in agnathans (jawless fish) and of immunoglobulin gene segments in gnathostomes (jawed vertebrates).