The cyanobacterial circadian oscillator can be reconstituted in vitro by mixing three purified clock proteins, KaiA, KaiB and KaiC, with ATP. The KaiC phosphorylation rhythm persists for at least 10 days without damping. By mixing oscillatory samples that have different phases and analyzing the dynamics of their phase relationships, we found that the robustness of the KaiC phosphorylation rhythm arises from the rapid synchronization of the phosphorylation state and reaction direction (phosphorylation or dephosphorylation) of KaiC proteins. We further demonstrate that synchronization is tightly linked with KaiC dephosphorylation and is mediated by monomer exchange between KaiC hexamers during the early dephosphorylation phase. This autonomous synchronization mechanism is probably the basis for the resilience of the cyanobacterial circadian system against quantitative fluctuations in clock components during cellular events such as cell growth and division.