The Nef protein of primate lentiviruses downregulates the cell surface expression of CD4 through a two-step process. First, Nef connects the cytoplasmic tail of CD4 with adaptor protein complexes (AP), thereby inducing the formation of CD4-specific clathrin-coated pits that rapidly endocytose the viral receptor. Second, Nef targets internalized CD4 molecules for degradation. Here we show that Nef accomplishes this second task by acting as a connector between CD4 and the β subunit of COPI coatomers in endosomes. A sequence encompassing a critical acidic dipeptide, located nearby but distinct from the AP-binding determinant of HIV-1 Nef, is responsible for β-COP recruitment and for routing to lysosomes. A novel class of endosomal sorting motif, based on acidic residues, is thus revealed, and β-COP is identified as its downstream partner.