Retromer is a heteromeric protein complex with important roles in endosomal membrane trafficking, most notably in the retrograde transport of lysosomal hydrolase receptors from endosomes to the Golgi. The core of retromer is composed of three subunits vacuolar protein sorting (Vps)35, Vps26 and Vps29, and in mammals, there are two paralogues of the medium subunit Vps26A and Vps26B. We find that both Vps26A and Vps26B bind to Vps35/Vps29 with nanomolar affinity and compete for a single-binding site to define distinct retromer complexes in vitro and in vivo. We have determined the crystal structure of mouse Vps26B and compare this structure with that of Vps26A. Vps26 proteins have a striking similarity to the arrestin family of proteins that regulate the signalling and endocytosis of G-protein-coupled receptors, although we observe that surface residues involved in arrestin function are not conserved in Vps26. Using structure-based mutagenesis, we show that both Vps26A and Vps26B are incorporated into retromer complexes through binding of Vps35 to a highly conserved surface patch within the C-terminal subdomain and that this interaction is required for endosomal recruitment of the proteins.