Archaeological, palaeontological and geological evidence shows that post-glacial warming released human populations from their various climate-bound refugia. Yet specific connections between these refugia and the timing and routes of post-glacial migrations that ultimately established modern patterns of genetic variation remain elusive. Here, we use Y-chromosome markers combined with autosomal data to reconstruct population expansions from regional refugia in Southwest Asia. Populations from three regions in particular possess distinctive autosomal genetic signatures indicative of likely refugia: one, in the north, centered around the eastern coast of the Black Sea, the second, with a more Levantine focus, and the third in the southern Arabian Peninsula. Modern populations from these three regions carry the widest diversity and may indeed represent the most likely descendants of the populations responsible for the Neolithic cultures of Southwest Asia. We reveal the distinct and datable expansion routes of populations from these three refugia throughout Southwest Asia and into Europe and North Africa and discuss the possible correlations of these migrations to various cultural and climatic events evident in the archaeological record of the past 15,000 years.