A complex cell-to-cell communication between the male pollen tube and the female reproductive organs is required for plant fertilization. A family of Catharanthus roseus Receptor Kinase-1 (CrRLK1L) membrane receptors has been genetically implicated in this process. Here we present crystal structures of the CrRLK1Ls ANXUR1 and 2 at 1.48 and 1.1 Å resolution, respectively. Our structures reveal a novel arrangement of two malectin-like domains connected by a short β-hairpin linker and stabilized by calcium ions. The canonical carbohydrate interaction surfaces of related animal and bacterial carbohydrate binding modules are not conserved among plant CrRLK1Ls. In line with this, we failed to detect binding of chemically diverse oligosaccharides to ANXUR1 and HERCULES1. Instead, CrRLK1Ls have evolved a protein-protein interface between their malectin domains, which forms a deep cleft lined by highly conserved aromatic and polar residues. Analysis of the glycosylation pattern of different CrRLK1Ls and their oligomeric states together suggests that this cleft could resemble a binding site for a ligand required for CrRLK1Ls receptor activation.