As NATO winds down its military mission in Afghanistan, it is turning its attention toward the Middle East. With the EU looking inward because of the euro crisis, NATO is the only organization with the interest and clout to bring together the countries of that important and unstable region in Europe’s neighborhood.

As the alliance’s leading member, the United States still brings a lot of pressure to bear on relations there—despite its pivot to Asia. Yet the Europeans—who, after all, make up the overwhelming majority of NATO members—should recognize the vital interest they have in good relations among their Middle Eastern neighbors.

Despite the current upheaval in the region, NATO believes it should deepen its cooperation with the North African and Middle Eastern countries through its Mediterranean Dialogue. The initiative, which involves seven non-NATO countries (Algeria, Egypt, Israel, Jordan, Mauritania, Morocco, and Tunisia), was set up in the mid 1990s during the halcyon days of the Oslo peace accords, when huge hope was invested in resolving the Israeli-Palestinian conflict.

Since then, the dialogue has had many ups and downs, not least because of the strains between Arab countries and Israel.

The Arab Spring should have provided the Mediterranean Dialogue with fresh impetus. That did not happen. The main reason is the highly emotional and complex dispute between Israel and Turkey, two of America’s most important allies in the region. The longer this dispute continues, the more damage it will cause to NATO, Turkey, and Israel.

The fallout between Israel and Turkey goes back to May 2010, when Israeli marines boarded the Mavi Marmara aid ship in international waters, killing nine Turks. The organizers of the aid mission, NGOs from Turkey, had wanted to break Israel’s naval blockade of the Gaza Strip in a gesture of support to Palestinians in Gaza.

That incident severed the Israeli-Turkish relationship that had been nurtured so carefully throughout the 1990s. Previously, the two countries had shared intelligence. Their militaries had cooperated. Israeli fighter jets had been able to use Turkish air space for exercises and, indeed, for snooping over Turkey’s vast eastern borders. Israel had upgraded Turkey’s fighter jets.

For Israel, the idea of having such closer relations with a secular Muslim, non-Arab country was always part of its strategy in that part of the Middle East. It suited Turkey too, given Ankara’s pro-U.S. and pro-NATO stance during those years.

But after Recep Tayyip Erdoğan’s Islamist Justice and Development Party came to power in 2002, relations became more strained. As prime minister, Erdoğan increasingly tried to score points with Arab countries by criticizing Israel over its policies vis-à-vis the Palestinians.

The Israeli-Turkish dispute had serious repercussions for NATO, too. The Mediterranean Dialogue became hostage to the dispute. The last meeting of substance took place in 2008, when NATO hosted a meeting of the region’s foreign ministers.

U.S. President Barack Obama’s administration, which recognizes Turkey’s strategic role in the region, tried to break the deadlock between the two countries. During his visit to Jerusalem two months ago, Obama persuaded Israeli Prime Minister Benjamin Netanyahu to apologize to Erdoğan for the Mavi Marmara incident.

That, however, was not enough to kick-start the Mediterranean Dialogue. Israel has not paid any compensation to the victims’ families yet, and full diplomatic relations have not been reestablished. Erdoğan quashed plans by NATO to host a gathering of Mediterranean Dialogue foreign ministers last month in Brussels, where NATO foreign ministers were meeting. Interestingly, Tunisia and Egypt supported Turkey’s actions, an indication of Ankara’s political clout in the region. It also shows that the Arab Spring has not lessened the region’s antipathy toward Israel.

This has left NATO in a quandary.

NATO needs Turkey because of its growing strategic role in the region and its importance to the alliance as a major military power. Turkey needs NATO because of the military role provided by the United States in particular and the alliance in general. NATO and Israel need each other in order to strengthen their intelligence ties. Besides, Israel sees the security advantages of a stronger Mediterranean Dialogue.

NATO could play a more assertive role in ending the Turkish-Israeli dispute. The alliance cannot continue pretending that the Israeli-Palestinian conflict is irrelevant to its interests in the region.

It is time, too, for Secretary General Anders Fogh Rasmussen to criticize Erdoğan’s anti-Zionist statements. Last month, in an interview with a Danish newspaper, the Turkish leader compared Zionism with a crime against humanity. When challenged about it, he said he was misquoted.

The EU does not have the clout to be an effective mediator between Israel and Turkey. It has to hope that NATO, with the aid of the United States, finds a path toward reconciliation between Europe’s two important neighbors. That is in the interests not only of the countries in the region, but of Europe, too. The Middle East is too volatile to allow this relationship to fester.