Historians often look for genealogies of nationalism in Austro-Hungarian and Ottoman imperial history. In this article, I use an inter-imperial framework to argue that the formative period of contemporary Eastern Mediterranean-European regionalism was the last five decades of these two empires. The diplomatic, economic and cultural relations between the two middle powers compose an alternative history to national narratives. I show that dualism ('independence' within empire) was an attractive imperial reform model for Ottoman Muslim intellectuals. I describe first a forgotten Egyptian-Ottoman dualist vision, and then I analyse the more well-known Arab-Turkish dualist plans up to 1921.