The nef gene of human and simian immunodeficiency virus is a key factor in acquired immunodeficiency syndrome pathogenesis and virus replication. Several Nef-induced phenomena, including the down-regulation of CD4 molecule, have been previously reported. In this study, we have identified and cloned a novel cellular protein Naf1 (Nef-associated factor 1), which associated with Nef in the yeast two-hybrid system and pull-down assay. The Naf1 gene generates two isoforms (Naf1alpha and beta) containing four coiled-coil structures. The Naf1 mRNA is ubiquitously expressed in human tissues with strong expression in peripheral blood lymphocytes and spleen. Naf1 overexpression increased cell surface CD4 expression. Nef suppressed this Naf1-induced augmentation of CD4 expression, providing a novel mode of Nef action in CD4 down-regulation.