The Lesser kestrel (Falco naumanni) evolved as a separate species in the Old-World kestrel radiation starting in the late Miocene. Given that the first cities were erected in the Holocene, this urban colonial raptor has only become a major town dweller recently in its evolutionary history. Today, more than 95% of lesser kestrel colonies in Spain and other Mediterranean countries are on buildings, and the remaining few are on rocky outcrops, that may have been the original nesting substrate for this cavity-nesting bird. Lesser kestrel fossils are well represented in cave sites, and their paleontological distribution, spanning from the Early Paleolithic to the Epipaleolithic, agrees well with its current breeding distribution. According to classical sources, such as the works of Columella and Pliny the Elder, and the presence of a skeletal remain in a Roman villa near Madrid, lesser kestrels may have nested in buildings and in urban settings for at least 2000–2500 years. However, there are no surviving colonies in structures older than 1400 years in Andalusia, nor in Spain. For a sample of 349 colonies on ancient buildings, a majority of the structures had been erected between the 15th and 17th centuries, this putting a time limit of about 300-600 years to the existence of those seemingly immemorial colonies. For specific towns and buildings, written references for the presence of lesser kestrel colonies do not go back more than two centuries. In fact, the Cathedral of Sevilla may be the structure with the longest continuous occupation by lesser kestrels recorded up to present time, from 1834 to 2020. Lesser kestrels were possibly too common in human settlements in the past as to be noted as special. This may explain the scarcity of references to the species until the 19th century. In any case, the same lack of information affects the other major Eurasian urban birds, as no timeline exist for the urbanization process of any other bird species. We propose that lesser kestrels became urban breeders when both adequate cavities in buildings and cereal fields, where they capture their invertebrate prey, became available in their breeding range, several millennia ago. However, urban colonies, in contrast with the ones on stable geological substrates, have been forced to move from building to building when older ones became ruinous or were rebuilt, but new structures with suitable cavities became available throughout History.