Eukaryotic cells traffic proteins and lipids between different compartments using protein-coated vesicles and tubules. The retromer complex is required to generate cargo-selective tubulovesicular carriers from endosomal membranes. Conserved in eukaryotes, retromer controls the cellular localization and homeostasis of hundreds of transmembrane proteins, and its disruption is associated with major neurodegenerative disorders. How retromer is assembled and how it is recruited to form coated tubules is not known. Here we describe the structure of the retromer complex (Vps26-Vps29-Vps35) assembled on membrane tubules with the bin/amphiphysin/rvs-domain-containing sorting nexin protein Vps5, using cryo-electron tomography and subtomogram averaging. This reveals a membrane-associated Vps5 array, from which arches of retromer extend away from the membrane surface. Vps35 forms the 'legs' of these arches, and Vps29 resides at the apex where it is free to interact with regulatory factors. The bases of the arches connect to each other and to Vps5 through Vps26, and the presence of the same arches on coated tubules within cells confirms their functional importance. Vps5 binds to Vps26 at a position analogous to the previously described cargo- and Snx3-binding site, which suggests the existence of distinct retromer-sorting nexin assemblies. The structure provides insight into the architecture of the coat and its mechanism of assembly, and suggests that retromer promotes tubule formation by directing the distribution of sorting nexin proteins on the membrane surface while providing a scaffold for regulatory-protein interactions.