Adaptor protein (AP) complexes sort cargo into vesicles for transport from one membrane compartment of the cell to another. Four distinct AP complexes have been identified, which are present in most eukaryotes. We report the existence of a fifth AP complex, AP-5. Tagged AP-5 localises to a late endosomal compartment in HeLa cells. AP-5 does not associate with clathrin and is insensitive to brefeldin A. Knocking down AP-5 subunits interferes with the trafficking of the cation-independent mannose 6-phosphate receptor and causes the cell to form swollen endosomal structures with emanating tubules. AP-5 subunits can be found in all five eukaryotic supergroups, but they have been co-ordinately lost in many organisms. Concatenated phylogenetic analysis provides robust resolution, for the first time, into the evolutionary order of emergence of the adaptor subunit families, showing AP-3 as the basal complex, followed by AP-5, AP-4, and AP-1 and AP-2. Thus, AP-5 is an evolutionarily ancient complex, which is involved in endosomal sorting, and which has links with hereditary spastic paraplegia.