VARP and TBC1D5 are accessory/regulatory proteins of retromer-mediated retrograde trafficking from endosomes. Using an NMR/X-ray approach, we determined the structure of the complex between retromer subunit VPS29 and a 12 residue, four-cysteine/Zn++ microdomain, which we term a Zn-fingernail, two of which are present in VARP. Mutations that abolish VPS29:VARP binding inhibit trafficking from endosomes to the cell surface. We show that VARP and TBC1D5 bind the same site on VPS29 and can compete for binding VPS29 in vivo. The relative disposition of VPS29s in hetero-hexameric, membrane-attached, retromer arches indicates that VARP will prefer binding to assembled retromer coats through simultaneous binding of two VPS29s. The TBC1D5:VPS29 interaction is over one billion years old but the Zn-fingernail appears only in VARP homologues in the lineage directly giving rise to animals at which point the retromer/VARP/TBC1D5 regulatory network became fully established.