Retromer mediates endosomal retrieval of transmembrane proteins in all eukaryotes and was first discovered in yeast in complex with the Vps5 and Vps17 sorting nexins (SNXs). Cryoelectron tomography (cryoET) studies of Retromer-Vps5 revealed a pseudo-helical coat on membrane tubules where dimers of the Vps26 subunit bind Vps5 membrane-proximal domains. However, the Vps29 subunit is also required for Vps5-Vps17 association despite being far from the membrane. Here, we show that Vps5 binds both Vps29 and Vps35 subunits through its unstructured N-terminal domain. A Pro-Leu (PL) motif in Vps5 binds Vps29 and is required for association with Retromer on membrane tubules in vitro, and for the proper recycling of the Vps10 cargo in Saccharomyces cerevisiae. CryoET of Retromer tubules with Vps5-Vps17 heterodimers show a similar architecture to the coat with Vps5-Vps5 homodimers, however, the spatial relationship between Retromer units is highly restricted, likely due to more limited orientations for docking. These results provide mechanistic insights into how Retromer and SNX-BAR association has evolved across species.