This article provides a game theoretic analysis of how the candidacy of Cyprus for European Union (EU) membership presents an important challenge for both the Union's eastern enlargement plans and current international efforts aimed at resolving the Cyprus problem. The conclusions indicate that the Cypriot conflict has entered a very delicate period in its protracted and troublesome history characterized by a deadlock game. Strong domestic and international factors have created the conditions for each side to follow a non-cooperative strategy aimed at unilateral victory rather than a compromise. In this regard, the EU's promise to the Greek Cypriots of membership in the Union, regardless of the settlement of the Cyprus problem, serves as a side payment that enforces non-cooperative strategy. Likewise, Turkey's overwhelming military superiority in the region and its unconditional support for the Turkish Cypriots strengthens the Turkish side's rigid position in the Cyprus negotiations. Under these circumstances, it is argued that an influential third party like the United States is needed to coordinate the efforts of the UN and EU to move the two parties away form a deadlock game. This effort requires a package approach to the issues surrounding the Cyprus problem, the island's membership in the EU, and EU-Turkey relations.