Nef is a multifunctional virulence factor of primate lentiviruses that facilitates viral replication in the infected host. All known functions of Nef require that it be myristoylated at its N terminus. This reaction is catalyzed by N-myristoyltransferases (NMTs), which transfer myristate from myristoyl coenzyme A (myristoyl-CoA) to the N-terminal glycine of substrate proteins. Two NMT isoforms (NMT-1 and NMT-2) are expressed in mammalian cells. To provide a better mechanistic understanding of Nef function, we used biochemical and microsequencing techniques to isolate and identify Nef-associated proteins. Through these studies, NMT-1 was identified as an abundant Nef-associated protein. The Nef-NMT-1 complex is most likely a transient intermediate of the myristoylation reaction of Nef and is modulated by agents which affect the size of the myristoyl-CoA pool in the cell. We also examined two other proteins that bear an N-terminal myristoylation signal, human immunodeficiency virus type 1 Gag and Hck protein tyrosine kinase, and found that Gag bound preferentially the NMT-2 isoform, while Hck bound mostly to NMT-1. Recognition of different NMT isoforms by these viral and cellular substrate proteins suggests nonoverlapping roles for these enzymes in vivo and reveals a potential for the development of inhibitors that target the myristoylation of specific viral substrates more selectively.