We have identified the human papillomavirus (HPV) DNA replication initiation protein E1 as a tight-binding substrate of cyclin E/cyclin-dependent kinase (Cdk) complexes by using expression cloning. E1, a DNA helicase, collaborates with the HPV E2 protein in ori-dependent replication. E1 formed complexes with cyclin E in insect and mammalian cells, independent of Cdks and E2. Additional cyclins, including A-, B-, and F-type (but not D-type), interacted with the E1/E2 complex, and A- and E-type cyclin kinases were capable of phosphorylating E1 and E2 in vitro. Association with cyclins and efficient phosphorylation of E1 required the presence of a cyclin interaction motif (the RXL motif). E1 lacking the RXL motif displayed defects in E2-dependent HPV ori replication in vivo. Consistent with a role for Cdk-mediated phosphorylation in E1 function, an E1 protein lacking all four candidate Cdk phosphorylation sites still associated with E2 and cyclin E but was impaired in HPV replication in vitro and in vivo. Our data reveal a link between cyclin/Cdk function and activation of HPV DNA replication through targeting of Cdk complexes to the E1 replication-initiation protein and suggest a functional role for E1 phosphorylation by Cdks. The use of cyclin-binding RXL motifs is now emerging as a major mechanism by which cyclins are targeted to key substrates.