The milestones of the Early Islamic period were usually square stone slabs, which had been set into walls of structures along the roads. This is probably the reason why so few milestones are known today in the Islamic world, as opposed to the many Roman and Byzantine milestones recovered. Early Islamic sources account for four terms indicating road lengths: mile (amayal) = 1.5-2.5 km; marhala = a day's trip; farash = 3 miles; barid = post office = 12 miles.

Milestones of 'Abd al-Malik were found in several spots. At Khan al-Hatrura ('The Good Samaritan') a square stone slab (0.4 x 0.4 m) is inscribed with the number of miles (109) between this spot and Damascus. A large Khan, which was in use as late as the Jordanian rule, was built on the site, over the remains of a Byzantine monastery. In the area of Wadi Qelt a stone slab (0.4 x 0.4 m) marks the distance between this spot and Damascus (107 miles). At Abu Gosh an inscription, probably belonging to an inn and Mosque, states the distance from the village to Jerusalem (7 miles). This milestone probably belongs to the road leading from Lod-Ramla to Jerusalem (in the Abbasid period?). Another milestone, also belonging to the Lod-Ramla road, was found at Bab al-Wad, bearing the name of 'Abd al-Malik and the distance to Jerusalem (8 miles).