Human mobility impacts many aspects of a city, from its spatial structure to its response to an epidemic. It is also ultimately key to social interactions, innovation and productivity. However, our quantitative understanding of the aggregate movements of individuals remains incomplete. Existing models—such as the gravity law or the radiation model—concentrate on the purely spatial dependence of mobility flows and do not capture the varying frequencies of recurrent visits to the same locations. Here we reveal a simple and robust scaling law that captures the temporal and spatial spectrum of population movement on the basis of large-scale mobility data from diverse cities around the globe. According to this law, the number of visitors to any location decreases as the inverse square of the product of their visiting frequency and travel distance. We further show that the spatio-temporal flows to different locations give rise to prominent spatial clusters with an area distribution that follows Zipf’s law. Finally, we build an individual mobility model based on exploration and preferential return to provide a mechanistic explanation for the discovered scaling law and the emerging spatial structure. Our findings corroborate long-standing conjectures in human geography (such as central place theory and Weber’s theory of emergent optimality) and allow for predictions of recurrent flows, providing a basis for applications in urban planning, traffic engineering and the mitigation of epidemic diseases.