Since the end of the Cold War, NATO has sought to bolster its presence in the Middle East and reached out to Israel, along with a number of Arab states, to achieve that goal.
In November 2004, units from the Israel Defense Forces (IDF) took part in multinational military exercises with the North Atlantic Treaty Organization (NATO) and participated in anti-terror activities such as patrols in the eastern Mediterranean Sea.
Tha month, Israel also sent a senior IDF representative, operations directorate chief Major General Yisrael Ziv, to a military summit in Belgium held by the chiefs-of-staff of twenty-six NATO members and other countries with ties to the organization. Israel was asked to attend the summit to help NATO upgrade what it calls the "Mediterranean dialogue" that will hopefully raise the level of joint military operations in the region. Egypt, Jordan, Tunisia, Algeria, Morocco and Mauretania were also invited.
In March 2005, Israel and NATO conducted their first ever joint naval exercise in the Red Sea, coming one month after the first visit by NATO Secretary General Jaap de Hoop Scheffer to Israel. The exercise involved six ships from the Standing NATO Response Force Mine Counter-Measures Group 2 and was led by the Italian Artigliere-class frigate ITS Bersagliere and included German, Greek, Spanish and Turkish minehunters as well as an Italian minesweeper. The NATO ships performed search-and-rescue exercises with Israeli fast patrol boats.
"We have conducted a very basic joint search-and-rescue exercise, which is similar to the manueuvers we conduct bi-annually with the U.S.," said Lt.-Col. Yossi Shahaf, the Israeli Navy's Commander of the Red Sea Arena. "The novelty in the exercise was the fact it was conducted with NATO ships.”
In June 2005, Israeli forces joined fourteen NATO nations and about 2,000 soldiers to participate in a major three-week submarine escape and rescue exercise in Italy. Submarines from Italy, the Netherlands, Spain and Turkey also joined the exercise which featured units from Israel, Russia and Ukraine for the first time.
In July 2005, for the first time in Israel's history, IDF infantry troops trained with NATO during a two-and-a-half week exercise at the Yavoriv Training Center in Ukraine. Israel joined twenty-one other nations for the anti-terrorist exercises. During the drills, many of the NATO countries looked to the IDF for advice on combating terrorism in their own countries. The focus of this training was for peacekeeping strategies and Israel displayed many of its own methods of controlling urban conflict.
In October 2006, Israel agreed to provide support for NATO counter-terrorism patrols in the Mediterranean when it signed a cooperation pact with NATO. Israel was the first of seven Middle Eastern countries to accept the 2004 offer to join NATO and to agree to all the terms of cooperation.
In April 2008, NATO naval forces conducted a joint training exercise with their Israeli counterparts in the waters off Haifa. Three NATO boats and two Israeli missile boats - the INS Lahav, a Sa’ar 5 class corvette, and the INS Keshet, a Nirit class missile boat - participated in the exercise.