This paper, which covers the period of the 2004 Annan Plan and its rejection to date, places the Cyprus Problem in an International Relations theoretic framework. It searches for a “foreign policy outcome,” essentially a decision by the leaders of the Greek-Cypriot and Turkish-Cypriot communities, to politically reunite these two communities under the auspices of the UN. The paper provides a synthesis of the neo-liberal and the neoclassical realist paradigms, aiming to better interpret the existing experience and to shed light on the prospect of a future solution to the problem. The strategic environment for the Republic of Cyprus (RoC) and the Turkish Republic of Northern Cyprus (TRNC) is ‘permissive’ because the message sent by the international system for reunification does not require the use of hard power. The leaders of the two communities play a key role, although the strategic political culture in small states such as the TRNC is not developed and state-society relations are underdeveloped. Also, the civil society at large can play a role in influencing the leaders' images regarding the reunification opportunity.