The article examines why a comprehensive settlement to resolve the Cyprus problem has yet to be reached despite the existence of a positive incentive structure and the proactive involvement of regional and international organizations, including the European Union and the United Nations. To address this question, evidence from critical turning points in foreign policy decision-making in Turkey, Greece and the two communities in Cyprus is drawn on. The role of hegemonic political discourses is emphasized, and it is argued that the latter have prevented an accurate evaluation of incentives that could have set the stage for a constructive settlement. However, despite the political debacle in the Cypriot negotiations, success stories have emerged, such as the reactivation of the Committee for Missing Persons (CMP), a defunct body for almost 25 years, to become the most successful bi-communal project following Cyprus’s EU accession. Contradictory evidence in the Cypriot peace process is evaluated and policy lessons to be learned from the CMP ‘success story’ are identified.