Centromeres are the structural and functional foundation for kinetochore formation, spindle attachment, and chromosome segregation. In this study, we isolated factors required for centromere propagation using genome-wide RNA interference screening for defects in centromere protein A (CENP-A; centromere identifier [CID]) localization in Drosophila melanogaster. We identified the proteins CAL1 and CENP-C as essential factors for CID assembly at the centromere. CID, CAL1, and CENP-C coimmunoprecipitate and are mutually dependent for centromere localization and function. We also identified the mitotic cyclin A (CYCA) and the anaphase-promoting complex (APC) inhibitor RCA1/Emi1 as regulators of centromere propagation. We show that CYCA is centromere localized and that CYCA and RCA1/Emi1 couple centromere assembly to the cell cycle through regulation of the fizzy-related/CDH1 subunit of the APC. Our findings identify essential components of the epigenetic machinery that ensures proper specification and propagation of the centromere and suggest a mechanism for coordinating centromere inheritance with cell division.