Downregulation of major histocompatibility complex class I (MHC-I) by HIV-1 Nef protein is indispensable for evasion of protective immunity by HIV-1. Though it has been suggested that the N-terminal region of Nef contributes to the function by associating with a mu-1A subunit of adaptor protein 1, the structural basis of the interaction between Nef and mu-1A remains elusive. We found that a tripartite hydrophobic motif (Trp13/Val16/Met20) in the N terminus of Nef was required for the MHC-I downregulation. Importantly, the motif functioned as a noncanonical mu-1A-binding motif for the interaction with the tyrosine motif-binding site of the mu-1A subunit. Our findings will help understanding of how HIV-1 evades the antiviral immune response by selectively redirecting the cellular protein trafficking system.