In the ciliate Euplotes crassus, millions of new telomeres are synthesized by telomerase and polymerase α-primase during macronuclear development in mated cells. Concomitant with de novo telomere formation, telomerase assembles into higher-order complexes of 550 kDa, 1,600 kDa, and 5 MDa. We show here that telomerase is physically associated with the lagging-strand replication machinery in these complexes. Antibodies against DNA primase precipitated telomerase activity from all three complexes from mated cells but not the 280-kDa telomerase complex from vegetatively growing cells. Moreover, when telomerase was affinity purified, primase copurified with enzyme from mated cells but not with the 280-kDa vegetative complex. Thus, the association of telomerase and primase is developmentally regulated. Intriguingly, PCNA (proliferating cell nuclear antigen) was also found in the 5-MDa complex from mated cells. We therefore speculate that this complex is a complete telomere synthesis machine, while the smaller complexes are assembly intermediates. The physical association of telomerase and primase explains the coordinate regulation of telomeric G- and C-strand synthesis and the efficiency of telomere addition in E. crassus.