The AP-5 complex is a recently identified but evolutionarily ancient member of the family of heterotetrameric adaptor proteins (AP complexes). It is associated with two proteins that are mutated in patients with hereditary spastic paraplegia, SPG11 and SPG15. Here we show that the four AP-5 subunits can be coimmunoprecipitated with SPG11 and SPG15, both from cytosol and from detergent-extracted membranes, with a stoichiometry of ∼1:1:1:1:1:1. Knockdowns of SPG11 or SPG15 phenocopy knockdowns of AP-5 subunits: all six knockdowns cause the cation-independent mannose 6-phosphate receptor to become trapped in clusters of early endosomes. In addition, AP-5, SPG11, and SPG15 colocalize on a late endosomal/lysosomal compartment. Both SPG11 and SPG15 have predicted secondary structures containing α-solenoids related to those of clathrin heavy chain and COPI subunits. SPG11 also has an N-terminal, β-propeller-like domain, which interacts in vitro with AP-5. We propose that AP-5, SPG15, and SPG11 form a coat-like complex, with AP-5 involved in protein sorting, SPG15 facilitating the docking of the coat onto membranes by interacting with PI3P via its FYVE domain, and SPG11 (possibly together with SPG15) forming a scaffold.