Music is a fascinating topic for evolutionary theory, natural philosophy, and narrative construction: music is a highly valued feature of all known living cultures, pervading many aspects of daily life, playing many roles. And music is ancient. The oldest known musical instruments appear in the archaeological record from 40,000 years ago (40 Kya) and from these we can infer even earlier musical artefacts/activities, as yet unrepresented in the archaeological record. I argue that, following research couched in the social brain hypothesis framework, a theoretical basis is emerging for the proposition that the (incremental) evolution of proto-music took hold in the late mid-Pleistocene, roughly 400 Kya, and perhaps earlier. Subsequently, musical activities and traditions incrementally evolved throughout modernity (from 250 Kya onwards), global dispersal from Africa (currently thought to be from 60-100 Kya onwards), and the Holocene (from 12 Kya). In this article I provide an overview of recent research and a sketch of musicâ€™s evolutionary career. I identify avenues for future research, including work in the evolution of the emotions, and the application of signalling theory to music archaeology.