Initiation of DNA synthesis is triggered by the binding of proteins to replication origins. However, little is known about the order in which specific proteins associate with origin sites during the cell cycle. We show that in cycling cells there are at least two different nucleoprotein complexes at oriC. A factor for inversion stimulation (FIS)-bound nucleoprotein complex, present throughout the majority of the cell cycle, switches to an integration host factor (IHF)-bound form as cells initiate DNA replication. Coincident with binding of IHF, initiator DnaA binds to its previously unoccupied R3 site. In stationary phase, a third nucleoprotein complex forms. FIS is absent and inactive oriC forms a nucleoprotein structure containing IHF that is not observed in cycling cells. We propose that interplay between FIS and IHF aids assembly of initiation nucleoprotein complexes during the cell cycle and blocks initiation at inappropriate times. This exchange of components at replication origins is reminiscent of switching between pre- and post-replicative chromatin states at yeast ARS1.