Although the coupling between circadian and cell cycles allows circadian clocks to gate cell division and DNA replication in many organisms, circadian clocks were thought to function independently of cell cycle. Here, we show that DNA replication is required for circadian clock function in Neurospora. Genetic and pharmacological inhibition of DNA replication abolished both overt and molecular rhythmicities by repressing frequency (frq) gene transcription. DNA replication is essential for the rhythmic changes of nucleosome composition at the frq promoter. The FACT complex, known to be involved in histone disassembly/reassembly, is required for clock function and is recruited to the frq promoter in a replication-dependent manner to promote replacement of histone H2A.Z by H2A. Finally, deletion of H2A.Z uncoupled the dependence of the circadian clock on DNA replication. Together, these results establish circadian clock and cell cycle as interdependent coupled oscillators and identify DNA replication as a critical process in the circadian mechanism.