To facilitate viral infection and spread, HIV-1 Nef disrupts the surface expression of the viral receptor (CD4) and molecules capable of presenting HIV antigens to the immune system (MHC-I). To accomplish this, Nef binds to the cytoplasmic tails of both molecules and then, by mechanisms that are not well understood, disrupts the trafficking of each molecule in different ways. Specifically, Nef promotes CD4 internalization after it has been transported to the cell surface, whereas Nef uses the clathrin adaptor, AP-1, to disrupt normal transport of MHC-I from the TGN to the cell surface. Despite these differences in initial intracellular trafficking, we demonstrate that MHC-I and CD4 are ultimately found in the same Rab7(+) vesicles and are both targeted for degradation via the activity of the Nef-interacting protein, beta-COP. Moreover, we demonstrate that Nef contains two separable beta-COP binding sites. One site, an arginine (RXR) motif in the N-terminal alpha helical domain of Nef, is necessary for maximal MHC-I degradation. The second site, composed of a di-acidic motif located in the C-terminal loop domain of Nef, is needed for efficient CD4 degradation. The requirement for redundant motifs with distinct roles supports a model in which Nef exists in multiple conformational states that allow access to different motifs, depending upon which cellular target is bound by Nef.