The surface expression of MHC I is reduced in HIV-infected cells. We show that the Nef protein affects the intracellular sorting of HLA-A and -B molecules. In the presence of Nef, these proteins accumulate in the Golgi and colocalize with clathrin-coated vesicles. MHC I modulation relies on a tyrosine-based sorting signal located in the cytoplasmic domain of HLA-A and -B heavy chains. This cryptic sorting signal becomes operative only in the presence of Nef. Nef interacts with the medium (μ) subunit of AP adaptor complexes involved in the recognition of tyrosine-based sorting signals, likely facilitating the connection between MHC I and the clathrin-dependent sorting machinery.