Systematic prospection and excavations in the Rustaq region of northern Oman, approximately 45 km from the coast in the foothills of the Western Hajar Mountains, have revealed an unexpectedly dense record of Neolithic sites. Besides surface scatters of lithic artefacts, excavation at the site of Hayy al-Sarh recovered two stratified archaeological horizons (AHs). The upper horizon, AH I, contained pierced marine shells that provided an age of the archaeological material of about 6800 to 7500 years cal BP. Typologically the AH I lithic assemblage compares to the Suwayh facies defined at the coast 300 km to the east. Whether the marine shells and cultural affinities point towards exchange with coastal communities or possibly seasonal movement remains an open question at this state of research, but this new evidence for inland Neolithic settlement near Rustaq provides important new data that will help improve our understanding of spatial patterns of Neolithic demographic variability.