While authoritarianism studies have comparatively addressed the question of regime legitimation in recent years, the scholarly attention has still been almost exclusively on the challenges from within the nation-state. This methodologically nationalist view needs to be complemented by a perspective that systematically takes into account the international and, as this paper argues, the regional dimension of political challenges and related regime justification discourses. Drawing on historical (post-1955) and current insights (post-2005) from the Middle East with Arabic as a regional lingua franca, the paper examines the patterns in which authoritarian regimes react to charges from regionally influential players that they act against widely shared “Arab interests”. It is argued that it is the inter-linkage between these Arab regional processes of (de-)legitimation on the one hand and the respective domestic, nation-state related justification discourses on the other which are key to understand the ebb and flow of authoritarian politics in the Arab Middle East.