The worship of baetyls in antiquity is well documented in the Near East and the Mediterranean, archaeologically as well as historically. While such practices were also common in South-East Arabia, the archaeological information on it is still very limited. A boulder carved with a "trident" (a mark familiar from local Abiel coin issues), which came to light at the site of Mleiha, has a circular cavity on the side similar to those visible on stones and on an eagle statue from contemporary ed-Dur. This association suggests a religious context for the Mleiha petroglyph and thus a possible identification as a baetyl. The archaeological evidence for stone worship and associated cult practices from the SE-Arabian Mleiha / PIR A-C period (3rd century BCE - 3rd century CE) is reviewed and compared with ethnographic parallels and information from, among others sources, the Kitāb al-aṣnām (Book of Idols) by Hisham ibn al-Kalbi (737-819 CE).