The present day distribution of Y chromosomes bearing the haplogroup J1 M267(*)G variant has been associated with different episodes of human demographic history, the main one being the diffusion of Islam since the Early Middle Ages. To better understand the modes and timing of J1 dispersals, we reconstructed the genealogical relationships among 282 M267(*)G chromosomes from 29 populations typed at 20 YSTRs and 6 SNPs. Phylogenetic analyses depicted a new genetic background consistent with climate-driven demographic dynamics occurring during two key phases of human pre-history: (1) the spatial expansion of hunter gatherers in response to the end of the late Pleistocene cooling phases and (2) the displacement of groups of foragers/herders following the mid-Holocene rainfall retreats across the Sahara and Arabia. Furthermore, J1 STR motifs previously used to trace Arab or Jewish ancestries were shown unsuitable as diagnostic markers for ethnicity.