Variable lymphocyte receptors (VLRs) are recently discovered leucine-rich repeat (LRR) family proteins that mediate adaptive immune responses in jawless fish. Phylogenetically it is the oldest adaptive immune receptor and the first one with a non-immunoglobulin fold. We present the crystal structures of one VLR-A and two VLR-B clones from the inshore hagfish. The hagfish VLRs have the characteristic horseshoe-shaped structure of LRR family proteins. The backbone structures of their LRR modules are highly homologous, and the sequence variation is concentrated on the concave surface of the protein. The conservation of key residues suggests that our structures are likely to represent the LRR structures of the entire repertoire of jawless fish VLRs. The analysis of sequence variability, prediction of protein interaction surfaces, amino acid composition analysis, and structural comparison with other LRR proteins suggest that the hypervariable concave surface is the most probable antigen binding site of the VLR.