Approximately 500 million years ago, two types of recombinatorial adaptive immune systems (AISs) arose in vertebrates. The jawed vertebrates diversify their repertoire of immunoglobulin domain-based T and B cell antigen receptors mainly through the rearrangement of V(D)J gene segments and somatic hypermutation, but none of the fundamental AIS recognition elements in jawed vertebrates have been found in jawless vertebrates. Instead, the AIS of jawless vertebrates is based on variable lymphocyte receptors (VLRs) that are generated through recombinatorial usage of a large panel of highly diverse leucine-rich-repeat (LRR) sequences. Whereas the appearance of transposon-like, recombination-activating genes contributed uniquely to the origin of the AIS in jawed vertebrates, the use of activation-induced cytidine deaminase for receptor diversification is common to both the jawed and jawless vertebrates. Despite these differences in anticipatory receptor construction, the basic AIS design featuring two interactive T and B lymphocyte arms apparently evolved in an ancestor of jawed and jawless vertebrates within the context of preexisting innate immunity and has been maintained since as a consequence of powerful and enduring selection, most probably for pathogen defense purposes.