Background The down-regulation of the major histocompatibility complex class I (MHC-I) from the surface of infected cells by the Nef proteins of primate immunodeficiency viruses likely contributes to pathogenesis by providing evasion of cell-mediated immunity. HIV-1 Nef-induced down-regulation involves endosomal trafficking and a cooperative interaction between the cytoplasmic domain (CD) of MHC-I, Nef, and the clathrin adaptor protein complex-1 (AP-1). The CD of MHC-I contains a key tyrosine within the sequence YSQA that is required for down-regulation by Nef, but this sequence does not conform to the canonical AP-binding tyrosine-based motif Yxxφ, which mediates binding to the medium (μ) subunits of AP complexes. We previously proposed that Nef allows the MHC-I CD to bind the μ subunit of AP-1 (μ1) as if it contained a Yxxφmotif. Methods and Findings Here, we show that a direct interaction between the MHC-I CD/Nef and μ1 plays a primary role in the down-regulation of MHC-I: GST pulldown assays using recombinant proteins indicated that most of the MHC-I CD and Nef residues that are required for the down-regulation in human cells contribute to direct interactions with a truncated version of μ1. Specifically, the tyrosine residue of the YSQA sequence in the MHC-I CD as well as Nef residues E62-65 and P78 each contributed to the interaction between MHC-I CD/Nef and μ1 in vitro, whereas Nef M20 had little to no role. Conversely, residues F172/D174 and V392/L395 of the binding pocket on μ1 for Yxxφ motifs were required for a robust interaction. Conclusions These data indicate that the MHC-I cytoplasmic domain, Nef, and the C-terminal two thirds of the μ subunit of AP-1 are sufficient to constitute a biologically relevant interaction. The data also reveal an unexpected role for a hydrophobic pocket in μ1 for interaction with MHC-I CD/Nef.