The nature of human dispersals out of Africa has remained elusive due to the poor resolution of paleoecological data in direct association with remains of the earliest non-African peoples. Here, we report hominin and non-hominin mammalian tracks from an ancient lake deposit in the Arabian Peninsula, dated within the last interglacial. The findings, it is argued, likely represent the oldest securely dated evidence for Homo sapiens in Arabia. The paleoecological evidence indicates a well-watered semi-arid setting during human movements into the Nefud Desert of Saudi Arabia. We conclude that visitation to the lake was transient – likely serving as a place to drink and to forage – and that late Pleistocene human and mammalian migrations and landscape use patterns in Arabia were inexorably linked.