During early Ottoman rule, a fort, Qal'at al-Akhdar, was built at the site, part of the larger network of fortifications along the Hajj caravan route to Medina and Mecca.

[4] Al-Ukhaydir is first clearly mentioned in the early 13th century, during Ayyubid rule, by Syrian geographer Yaqut al-Hamawi, who noted that the Islamic prophet Muhammad prayed at the site on his way to Tabuk in 630.

[4] The 14th-century traveler Ibn Batuta remarked that Wadi al-Ukhaydir was isolated in the wilderness and referred to it as a "valley of hell" where many Hajj pilgrims had died one year because of a water shortage at the site.

Not long before then, a reservoir had been built at al-Ukhaydir, because in 1517 an anonymous source described intertribal fighting at the pool, which rendered it unusable by the Hajj pilgrims that year.

[5] As an unprotected rest stop and watering place on the Hajj route from Damascus to Medina, the Ottomans sought to fortify the site, along with numerous others throughout the 16th century.

A particularly urgent reason to fortify al-Ukhaydir was due to the poisoning of its reservoir with colocynth by a certain Mulhim, the chieftain of the Bedouin tribe of Banu Lam al-Mafarija, in 1530.

[6] To prevent recurrent sabotage by the Bedouin, including al-Mafarija[6] and Banu Uqbah,[2] Sultan Sulayman the Magnificent decreed the construction of a fort at al-Ukhaydir in 1531/32.

[6] Accordingly, the governor of Damascus, Mustafa Ablaq Pasha, commanded the Lajjun-based Arab strongman, Turabay ibn Qaraja, to build a fort at the site, which was completed in forty days.

[2] Twenty local Janissaries from Damascus were regularly posted at al-Ukhaydir, and a tax on pilgrims' goods was collected at the fort to contribute to the troops' wages.

[7] That year, French archaeologists A. Jaussen and R. Savignac carried out the first major excavation at al-Ukhaydir, producing photos, site plans and Arabic inscription squeezes.