Early endosomes sort transmembrane cargo either for lysosomal degradation or retrieval to the plasma membrane or the Golgi complex. Endosomal retrieval in eukaryotes is governed by the anciently homologous retromer or retriever complexes. Each comprises a core tri-protein subcomplex, membrane-deformation proteins and interacting partner complexes, together retrieving a variety of known cargo proteins. Trichomonas vaginalis, a sexually transmitted human parasite, uses the endomembrane system for pathogenesis. It has massively and selectively expanded its endomembrane protein complement, the evolutionary path of which has been largely unexplored. Our molecular evolutionary study of retromer, retriever and associated machinery in parabasalids and its free-living sister lineage of Anaeramoeba demonstrates specific expansion of the retromer machinery, contrasting with the retriever components. We also observed partial loss of the Commander complex and sorting nexins in Parabasalia but complete retention in Anaeramoeba. Notably, we identified putative parabasalid sorting nexin analogs. Finally, we report the first retriever protein localization in a non-metazoan group along with retromer protein localization in T. vaginalis.