Centrioles are microtubule-based structures that organize the centrosome and nucleate cilia. Centrioles duplicate once per cell cycle, and duplication requires Plk4, a member of the Polo-like kinase family; however, the mechanism linking Plk4 activity and centriole formation is unknown. In this study, we show in human and frog cells that Plk4 interacts with the centrosome protein Cep152, the orthologue of Drosophila melanogaster Asterless. The interaction requires the N-terminal 217 residues of Cep152 and the crypto Polo-box of Plk4. Cep152 and Plk4 colocalize at the centriole throughout the cell cycle. Overexpression of Cep152 (1–217) mislocalizes Plk4, but both Cep152 and Plk4 are able to localize to the centriole independently of the other. Depletion of Cep152 prevents both normal centriole duplication and Plk4-induced centriole amplification and results in a failure to localize Sas6 to the centriole, an early step in duplication. Cep152 can be phosphorylated by Plk4 in vitro, suggesting that Cep152 acts with Plk4 to initiate centriole formation.