During the Pre-Islamic era the city at the site was called "Hajr" (), and was reportedly founded by the tribe of Banu Hanifa. Hajr served as the capital of the province of Al Yamamah, whose governors were responsible for most of central and eastern Arabia during the Umayyad and Abbasid eras. Al-Yamamah broke away from the Abbasid Empire in 866 and the area fell under the rule of the Ukhaydhirites, who moved the capital from Hajr to nearby Al Kharj. The city then went into a long period of decline. In the 14th century, North African traveller Ibn Battuta wrote of his visit to Hajr, describing it as "the main city of Al-Yamamah, and its name is Hajr". Ibn Battuta goes on to describe it as a city of canals and trees with most of its inhabitants belonging to Bani Hanifa, and reports that he continued on with their leader to Mecca to perform the Hajj.