The generation of metameric body plans is a key process in development. In Drosophila segmentation, periodicity is established rapidly through the complex transcriptional regulation of the pair-rule genes. The 'primary' pair-rule genes generate their 7-stripe expression through stripe-specific cis-regulatory elements controlled by the preceding non-periodic maternal and gap gene patterns, whereas 'secondary' pair-rule genes are thought to rely on 7-stripe elements that read off the already periodic primary pair-rule patterns. Using a combination of computational and experimental approaches, we have conducted a comprehensive systems-level examination of the regulatory architecture underlying pair-rule stripe formation. We find that runt (run), fushi tarazu (ftz) and odd skipped (odd) establish most of their pattern through stripe-specific elements, arguing for a reclassification of ftz and odd as primary pair-rule genes. In the case of run, we observe long-range cis-regulation across multiple intervening genes. The 7-stripe elements of run, ftz and odd are active concurrently with the stripe-specific elements, indicating that maternal/gap-mediated control and pair-rule gene cross-regulation are closely integrated. Stripe-specific elements fall into three distinct classes based on their principal repressive gap factor input; stripe positions along the gap gradients correlate with the strength of predicted input. The prevalence of cis-elements that generate two stripes and their genomic organization suggest that single-stripe elements arose by splitting and subfunctionalization of ancestral dual-stripe elements. Overall, our study provides a greatly improved understanding of how periodic patterns are established in the Drosophila embryo.