The critical immortalizing activity of the human papillomavirus (HPV) type-16 E6 oncoprotein is to induce expression of hTERT, the catalytic and rate-limiting subunit of telomerase. Additionally, E6 binds to a cellular protein called E6-associated protein (E6-AP) to form an E3 ubiquitin ligase that targets p53 for proteasome-dependent degradation. Although telomerase induction and p53 degradation are separable and distinct functions of E6, binding of E6 to E6-AP strongly correlated with the induction of hTERT. Here, we demonstrate using shRNAs to reduce E6-AP expression that E6-AP is required for E6-mediated telomerase induction. A yeast two-hybrid screen to find new targets of the E6/E6-AP E3 ubiquitin ligase complex identified NFX1. Two isoforms of NFX1 were found: NFX1-123, which coactivated with c-Myc at the hTERT promoter, and NFX1-91, which repressed the hTERT promoter. NFX1-91 was highly ubiquitinated and destabilized in epithelial cells expressing E6. Furthermore, knockdown of NFX1-91 by shRNA resulted in derepression of the endogenous hTERT promoter and elevated levels of telomerase activity. We propose that the induction of telomerase by the HPV-16 E6/E6-AP complex involves targeting of NFX1-91, a newly identified repressor of telomerase, for ubiquitination and degradation.