HIV-1 Nef is an accessory protein necessary for HIV-1 virulence and rapid AIDS development. Nef promotes viral replication and infection by connecting CD4 and several other cell surface receptors to the clathrin adaptor protein AP2, resulting in the internalization and degradation of the receptors interacting with Nef. We investigated how Nef can mediate constitutive receptor endocytosis through the interaction of the dileucine motif in its C-terminal flexible loop (C-loop) with AP2, whereas AP2 binding of the transmembrane receptors usually results in an equilibrated (recycled) endocytosis. Our results indicated that in addition to the dileucine motif, there is a second motif in the Nef C-loop involved in the Nef-AP2 interaction. Nef-mediated CD4 downregulation was impaired when the residue in the hydrophobic region in the Nef C-loop (LL165HPMSLHGM173) was mutated to a basic residue K/R or an acidic residue E/D or to the rigid residue P, or when M168L170, L170H171, or G172M173 was mutated to AA. A pull-down assay indicated that AP2 was not coprecipitated with Nef mutants that did not downregulate CD4. Molecular modeling of the Nef C-terminal flexible loop in complex with AP2 suggests that M168L170 occupies a pocket in the AP2 σ2 subunit. Our data suggest a new model in the Nef-AP2 interaction in which the hydrophobic region in the Nef C-loop with the dileucine (L164L165) motif and M168L170 motif binds to AP2(σ2), while the acidic motif E174 and D175 binds to AP2(α), which explains how Nef through the flexible loop connects CD4 to AP2 for constitutive CD4 downregulation.