A HIV-1 Nef affinity column was used to purify a 35-kDa Nef-interacting protein from T-cell lysates. The 35-kDa protein was identified by peptide microsequence analysis as the human thioesterase II (hTE) enzyme, an enzyme previously identified in a yeast two-hybrid screen as a potential Nef-interacting protein. Immuno-fluorescence studies showed that hTE localizes to peroxisomes and that coexpression of Nef and hTE leads to relocalization of Nef to peroxisomes. Interaction of Nef and hTE was abolished by point mutations in Nef at residues Asp108, Leu112, Phe121, Pro122, and Asp123. All of these mutations also abrogated the ability of Nef to down-regulate CD4 from the surface of HIV-infected cells. Based on the x-ray and NMR structures of Nef, these residues define a surface on Nef critical for CD4 down-regulation. A subset of these mutations also affected the ability of Nef to down-regulate major histocompatibility complex class I. These results, taken together with previous studies, identify a region on Nef critical for most of its known functions. However, not all Nef alleles bind to hTE with high affinity, so the role of hTE during HIV infection remains uncertain.