Pre-Pottery Neolithic assemblages are best known from the fertile areas of the Mediterranean Levant. The archaeological site of Jebel Qattar 101 (JQ-101), at Jubbah in the southern part of the Nefud Desert of northern Saudi Arabia, contains a large collection of stone tools, adjacent to an Early Holocene palaeolake. The stone tool assemblage contains lithic types, including El-Khiam and Helwan projectile points, which are similar to those recorded in Pre-Pottery Neolithic A and Pre-Pottery Neolithic B assemblages in the Fertile Crescent. Jebel Qattar lies ~500 kilometres outside the previously identified geographic range of Pre-Pottery Neolithic cultures. Technological analysis of the typologically diagnostic Jebel Qattar 101 projectile points indicates a unique strategy to manufacture the final forms, thereby raising the possibility of either direct migration of Levantine groups or the acculturation of mobile communities in Arabia. The discovery of the Early Holocene site of Jebel Qattar suggests that our view of the geographic distribution and character of Pre-Pottery Neolithic cultures may be in need of revision.