Gene regulatory networks govern pattern formation and differentiation during embryonic development. Segmentation of somites, precursors of the vertebral column among other tissues, is jointly controlled by temporal signals from the segmentation clock and spatial signals from morphogen gradients. To explore how these temporal and spatial signals are integrated, we combined time-controlled genetic perturbation experiments with computational modeling to reconstruct the core segmentation network in zebrafish. We found that Mesp family transcription factors link the temporal information of the segmentation clock with the spatial action of the fibroblast growth factor signaling gradient to establish rostrocaudal (head to tail) polarity of segmented somites. We further showed that cells gradually commit to patterning by the action of different genes at different spatiotemporal positions. Our study provides a blueprint of the zebrafish segmentation network, which includes evolutionarily conserved genes that are associated with the birth defect congenital scoliosis in humans.