This paper explores the techniques and strategies used by Ottoman authorities to control the Bedouin with a specific focus on the province of Hijaz between 1840 and 1908. Using primary sources from the Ottoman and British archives, it argues that the Ottoman Empire developed a ‘politics of negotiation’ towards the tribes in its attempt to secure cities and major pilgrimage and trade routes against tribal attack. The principal agents of the empire who made this negotiated governance possible were the amir of Mecca and the governor of Hijaz. To the contrary of what Albert Hourani articulated as the 'politics of notables', a differentiation between the 'indigenous' and 'imperial' actors, or between the Arab and non-Arabs, does not help us to understand the nature of this negotiation. Most of the so-called indigenous actors were the agents of the empire to negotiate with the tribes and to maintain the imperial order in the region. In this regard, contrary to what Hourani suggested, conflict between amir and governor, or the contrast between Hijazis and the Ottoman government, did not constitute the foundations of the politics in Hijaz. Rather, amirs and governors were the agents of the Ottoman Empire who aimed at maintaining order in the province through a politics of negotiation with the tribes. Rather than clashing with each other for supremacy, they dealt with the Bedouin, who posed the most serious challenges to imperial order. Using the local notables and its bureaucrats as its agents, the government allocated grain allowances to the tribes and salaried their chiefs in return for their service on behalf of the state in their territories. Imperial authorities used these incentives as effective instruments of negotiation and as weapons for bringing tribes back into line when they disturbed the order. But the latter was in the Bedouins’ benefit, it was the most influential means by which they could coerce the state into carrying out their demands.