I argue that patron-client networks linking local autocrats to foreign patrons can help explain the varying durability of autocratic regimes in the Middle East by way of exposing the origins of their ruling coalitions--critical social bases that profoundly influenced the direction of state-building efforts in the post-colonial era. Comparing six cases (Kuwait, Tunisia, Jordan, Bahrain, Iran, and Iraq), this paper scrutinizes the choices made by authoritarian incumbents during the early stages of regime consolidation. I posit a systematic argument: the more foreign patrons intervened to augment the capacity of dictators to crush political challengers early on, the greater the incentive these leaders faced in consolidating power through exclusionary means--that is, by building narrower coalitions that refused to trade power for loyalty while neglecting to construct institutional arrangements to foreclose future contestation. Conversely, autocrats that did not experience pervasive exogenous impositions during early struggles tended to anchor their authority in broader coalitions defined by costly bargained side-payments linking popular sectors to the regime's authoritarian perpetuity. Cross-regional comparisons may reveal that while geopolitical constraints cast long shadows over post-colonial state-building, they shape the coalitional lineaments of autocratic rule in very different ways.