HIV-1 Nef is a desirable vaccine component because it is expressed early and abundantly during HIV infection, and contains many CTL, T-helper cell, and B-cell epitopes. Nef, however, down-regulates MHC-1 and CD4 cell surface expression, contributing to viral escape from host immunity. To prevent Nef from down-regulating both MHC-1 and CD4 while preserving most CTL epitopes, a panel of Nef mutants was constructed and assessed. Some mutants, as expected, modulated either MHC-1 or CD4 expression. Others prevented down-regulation of both proteins but sacrificed numerous immunogenic epitopes. Deletion of 19 N-terminal amino acids including the myristoylation signal from Nef completely abrogated both MHC-1 and CD4 down-regulation while preserving most CTL, T-helper and B-cell epitopes. Our results demonstrate that the myristoylation signal in the Nef protein is critical for Nef-mediated endocytosis of both MHC-1 and CD4. Non-myristoylated Nef containing a full complement of CTL epitopes has greater potential as a vaccine component than wild-type Nef.