Ubiquitination of the chemokine receptor CXCR4 serves as a targeting signal for lysosomal degradation, but the mechanisms mediating ubiquitination and lysosomal sorting remain poorly understood. Here we report that the Nedd4-like E3 ubiquitin ligase AIP4 mediates ubiquitination of CXCR4 at the plasma membrane, and of the ubiquitin binding protein Hrs on endosomes. CXCR4 activation promotes CXCR4 colocalization with AIP4 and Hrs within the same region of endosomes. Endosomal sorting of CXCR4 is dependent on Hrs as well as the AAA ATPase Vps4, the latter involved in regulating the ubiquitination status of both CXCR4 and Hrs. We propose a model whereby AIP4, Hrs, and Vps4 coordinate a cascade of ubiquitination and deubiquitination events that sort CXCR4 to the degradative pathway.