Recent fieldwork conducted along the Tihâma coastal plain has illuminated a late prehistoric megalithic culture that extends the length of the Red Sea coast of Yemen. To date, seven sites comprising megalithic elements have been documented in the region. These imposing monuments dated from the late third to the early second millennium BC appear to be strategically located at precise points along major wâdî systems. Given the absence of stone in the area, these large stone monuments would have been carried over long distances, making it highly probable that both the stone and monuments were meaningful. This culturally charged landscape evokes the marking of territorial or sacred space in the periods preceding the rise of the South Arabian kingdoms. In the late second and early first millennium BC, the same megaliths were re-used in the foundations of monumental structures and as grave markers. Currently the same stones can be seen marking the graves and tombs of Muslim âwlîya or saints and incorporated into the architecture of mosques in the surrounding areas. The re-use of these stones in sacred places such as mosques and âwlîya tombs suggest that not only were these stones and the spaces created around them significant in the past but that they continue to be. This paper discusses the way these megalithic complexes were used as a way of marking and identifying with territory and space in the late prehistoric period and the way that they continue to be a part of Islamic sacred space and of a wider regional Tihâman identity today.