There is now compelling evidence that many arthropods pattern their segments using a clock-and-wavefront mechanism, analogous to that operating during vertebrate somitogenesis. In this Review, we discuss how the arthropod segmentation clock generates a repeating sequence of pair-rule gene expression, and how this is converted into a segment-polarity pattern by 'timing factor' wavefronts associated with axial extension. We argue that the gene regulatory network that patterns segments may be relatively conserved, although the timing of segmentation varies widely, and double-segment periodicity appears to have evolved at least twice. Finally, we describe how the repeated evolution of a simultaneous (Drosophila-like) mode of segmentation within holometabolan insects can be explained by heterochronic shifts in timing factor expression plus extensive pre-patterning of the pair-rule genes.