High-risk human papillomaviruses (HPV) are linked to human cervical and other ano-genital cancers. Integration of the viral genome in the transformed epithelial cells is restricted to the coding regions for the E6 and E7 oncoproteins. Nevertheless, E7 plays the major role in cell transformation. We report a novel interaction between HPV-16 E7 and the Nm23-H1 and Nm23-H2 proteins identified in yeast by the two-hybrid system and confirmed by co-immunoprecipitation in the human keratinocyte HaCaT cell line. Expression of the E7 oncoprotein in HaCaT cells induces modified keratinocyte proliferation and differentiation patterns, and leads to down-modulation and functional inactivation of the metastasis suppressor Nm23-H1 protein. Both transcriptional down-regulation and protein degradation contribute to reduce Nm23-H1 intracellular content. Besides metastasis suppression, Nm23-H1 displays multiple functions in cell cycle regulation and differentiation, development, DNA regulation and caspase-independent apoptosis. As a consequence of Nm23-H1 inhibition, HPV-16 E7 expressing HaCaT cells, acquire invasiveness capabilities and resistance to granzyme A-induced apoptosis. We propose that impairment of the multifunctional role of Nm23-H1 is an important feature consistent with the complex strategy carried out by HPV-16 E7 to promote cell transformation and tumor progression.