Due to the limited coding capacity of their small genomes, human papillomaviruses (HPV) rely extensively on host factors for the completion of their life cycles. Accordingly, most HPV proteins, including the replicative helicase E1, engage in multiple protein interactions. The fact that conserved regions of E1 have not yet been ascribed a function prompted us to use tandem affinity protein purification (TAP) coupled to mass spectrometry to identify novel targets of this helicase. This method led to the discovery of a novel interaction between the N-terminal 40 amino acids of HPV type 11 (HPV11) E1 and the cellular WD repeat protein p80 (WDR48). We found that interaction with p80 is conserved among E1 proteins from anogenital HPV but not among cutaneous or animal types. Colocalization studies showed that E1 can redistribute p80 from the cytoplasm to the nucleus in a manner that is dependent on the E1 nuclear localization signal. Three amino acid substitutions in E1 proteins from HPV11 and -31 were identified that abrogate binding to p80 and its relocalization to the nucleus. In HPV31 E1, these substitutions reduced but did not completely abolish transient viral DNA replication. HPV31 genomes encoding two of the mutant E1 proteins were not maintained as episomes in immortalized primary keratinocytes, whereas one encoding the third mutant protein was maintained at a very low copy number. These findings suggest that the interaction of E1 with p80 is required for efficient maintenance of the viral episome in undifferentiated keratinocytes.