The Drosophila embryo transiently exhibits a double segment periodicity, defined by the expression of seven "pair-rule" genes, each in a pattern of seven stripes. At gastrulation, interactions between the pair-rule genes lead to frequency doubling and the patterning of fourteen parasegment boundaries. In contrast to earlier stages of Drosophila anteroposterior patterning, this transition is not well understood. By carefully analysing the spatiotemporal dynamics of pair-rule gene expression, we demonstrate that frequency-doubling is precipitated by multiple coordinated changes to the network of regulatory interactions between the pair-rule genes. We identify the broadly expressed but temporally patterned transcription factor, Odd-paired (Opa/Zic), as the cause of these changes, and show that the patterning of the even-numbered parasegment boundaries relies on Opa-dependent regulatory interactions. Our findings indicate that the pair-rule gene regulatory network has a temporally-modulated topology, permitting the pair-rule genes to play stage-specific patterning roles.