This article 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. As a result of this policy, imperial authorities had to give significant concessions to the tribes, and they thus incorporated them into the province's imperial order. When the Ottoman economy went through a crisis, as in the 1900s, negotiated governance and order faced great problems.