Nef is an HIV-encoded accessory protein that enhances pathogenicity by down-regulating major histocompatibility class I (MHC-I) expression to evade killing by cytotoxic T lymphocytes (CTLs). A potent Nef inhibitor that restores MHC-I is needed to promote immune-mediated clearance of HIV-infected cells. We discovered that the plecomacrolide family of natural products restored MHC-I to the surface of Nef-expressing primary cells with variable potency. Concanamycin A (CMA) counteracted Nef at subnanomolar concentrations that did not interfere with lysosomal acidification or degradation and were nontoxic in primary cell cultures. CMA specifically reversed Nef-mediated down-regulation of MHC-I, but not CD4, and cells treated with CMA showed reduced formation of the Nef:MHC-I:AP-1 complex required for MHC-I down-regulation. CMA restored expression of diverse allotypes of MHC-I in Nef-expressing cells and inhibited Nef alleles from divergent clades of HIV and simian immunodeficiency virus, including from primary patient isolates. Lastly, we found that restoration of MHC-I in HIV-infected cells was accompanied by enhanced CTL-mediated clearance of infected cells comparable to genetic deletion of Nef. Thus, we propose CMA as a lead compound for therapeutic inhibition of Nef to enhance immune-mediated clearance of HIV-infected cells.