Retromer is a trimeric protein complex of Vps29, Vps35 and Vps26 that mediates endosomal retrieval of transmembrane proteins in all eukaryotes. It was first discovered in yeast and shown to form a heteropentameric complex with the sorting nexins (SNXs) Vps5 and Vps17, and subsequent cryoelectron tomographic (cryoET) studies showed that Retromer can assemble via its Vps26 subunit on top of the membrane-bound bin/amphiphysin/rvs (BAR) domains of these SNX-BAR proteins to generate a tubular membrane coat. However, the Vps29 subunit, which is distal to the membrane surface, is also known to be important for Vps5-Vps17 interactions in situ. Here, we show that the association of yeast Retromer and SNX-BAR proteins requires a series of discrete interactions. The mechanism is similar, although slightly different, across various yeast species and involves a high affinity interaction between the N-terminal unstructured domain of Vps5 with both Vps29 and Vps35 Retromer subunits. A Pro-Leu (PL) motif in Vps5 mediates binding to Vps29, and structure-based mutations demonstrate that it is required for subsequent association of Retromer with the Vps5-Vps17 heterodimer on membrane tubules in vitro, and for the proper recycling of the Vps10 cargo in Saccharomyces cerevisiae. This motif binds specifically to a conserved hydrophobic pocket of Vps29, which in humans is known to recruit other regulatory proteins such as TBC1D5, VARP, and the VPS35L subunit of Retriever. The motif is unique to Vps5 and not found in other SNX-BAR family members, including human SNX1 and SNX2 orthologues which likely explains their inability to associate with high affinity with Retromer like their yeast counterparts. Our data provides a mechanistic explanation for how Retromer and SNX-BAR association has evolved across species.