Variable lymphocyte receptors (VLRs) are leucine-rich repeat proteins that mediate adaptive immunity in jawless vertebrates. VLRs are fundamentally different from the antibodies of jawed vertebrates, which consist of immunoglobulin (Ig) domains. We determined the structure of an anti–hen egg white lysozyme (HEL) VLR, isolated by yeast display, bound to HEL. The VLR, whose affinity resembles that of IgM antibodies, uses nearly all its concave surface to bind the protein, in addition to a loop that penetrates into the enzyme active site. The VLR–HEL structure combined with sequence analysis revealed an almost perfect match between ligand-contacting positions and positions with highest sequence diversity. Thus, it is likely that we have defined the generalized antigen-binding site of VLRs. We further demonstrated that VLRs can be affinity-matured by 13-fold to affinities as high as those of IgG antibodies, making VLRs potential alternatives to antibodies for biotechnology applications.