House sparrows (Passer domesticus) are a hugely successful anthrodependent species; occurring on nearly every continent. Yet, despite their ubiquity and familiarity to humans, surprisingly little is known about their origins. We sought to investigate the evolutionary history of the house sparrow and identify the processes involved in its transition to a human-commensal niche. We used a whole genome resequencing dataset of 120 individuals from three Eurasian species, including three populations of Bactrianus sparrows, a non-commensal, divergent house sparrow lineage occurring in the Near East. Coalescent modelling supports a split between house and Bactrianus sparrow 11 Kya and an expansion in the house sparrow at 6 Kya, consistent with the spread of agriculture following the Neolithic revolution. Commensal house sparrows therefore likely moved into Europe with the spread of agriculture following this period. Using the Bactrianus sparrow as a proxy for a pre-commensal, ancestral house population, we performed a comparative genome scan to identify genes potentially involved with adaptation to an anthropogenic niche. We identified potential signatures of recent, positive selection in the genome of the commensal house sparrow that are absent in Bactrianus populations. The strongest selected region encompasses two major candidate genes; COL11A – which regulates craniofacial and skull development and AMY2A, part of the amylase gene family which has previously been linked to adaptation to high-starch diets in humans and dogs. Our work examines human-commensalism in an evolutionary framework, identifies genomic regions likely involved in rapid adaptation to this new niche and ties the evolution of this species to the development of modern human civilization.