Studies of self-organising groups like schools of fish or flocks of birds have sought to uncover the behavioural rules individuals use (local-level interactions) to coordinate their motion (global-level patterns). However, empirical studies tend to focus on short-term or one-off observations where coordination has already been established, or describe transitions between different coordinated states. As a result, we have a poor understanding of how behavioural rules develop and are maintained in groups. Here, we study the emergence and repeatability of coordinated motion in shoals of stickleback fish (Gasterosteus aculeatus). Shoals were introduced to a simple environment, where their spatio-temporal position was deduced via video analysis. Using directional correlation between fish velocities and wavelet analysis of fish positions, we demonstrate how shoals that are initially uncoordinated in their motion quickly transition to a coordinated state with defined individual leader-follower roles. The identities of leaders and followers were repeatable across two trials, and coordination was reached more quickly during the second trial, and by groups of fish with higher mean levels of activity. The rapid emergence of coordinated motion and repeatability of social roles in stickleback fish shoals may act to reduce uncertainty of social interactions in the wild, where individuals live in a system with high fission-fusion dynamics and non-random patterns of association.