Between 10 and six thousand years ago the Arabian Peninsula saw the most recent of the ‘Green Arabia’ periods, when increased rainfall transformed this generally arid region. The transition to the Neolithic in Arabia occurred during this period of climatic amelioration. Various forms of stone structures are abundant in northern Arabia, and it has been speculated that some of these dated to the Neolithic, but there has been little research on their character and chronology. Here we report a study of 104 ‘mustatil’ stone structures from the southern margins of the Nefud Desert in northern Arabia. We provide the first chronometric age estimate for this type of structure – a radiocarbon date of ca. 5000 BC – and describe their landscape positions, architecture and associated material culture and faunal remains. The structure we have dated is the oldest large-scale stone structure known from the Arabian Peninsula. The mustatil phenomenon represents a remarkable development of monumental architecture, as hundreds of these structures were built in northwest Arabia. This ‘monumental landscape’ represents one of the earliest large-scale forms of monumental stone structure construction anywhere in the world. Further research is needed to understand the function of these structures, but we hypothesise that they were related to rituals in the context of the adoption of pastoralism and resulting territoriality in the challenging environments of northern Arabia.