The year 1956 was full of events which significantly influenced the geostrategic situation in Europe. In February, the opening of the 20th congress of the Soviet Communist Party marked the beginning of the "destalinizations." In March, both Tunisia and Morocco became independent. In July, the President of Egypt Gamal Abd El Nasser nationalised the Suez Canal. In October, the Hungarian people's rebellion started, repressed by a Soviet intervention. Almost simultaneously the Suez crisis was escalated by the Israeli "Sinai campaign" followed by the French-British intervention, which was not approved by the U.S. The Alliance's solidarity seemed to reach the lowest level just as the Cold War was reaching a peak.
The following years saw a growing Soviet political penetration in the Mediterranean, while Western influence in North Africa and the Middle East was noticeably reduced. Cyprus became independent in 1960, followed by Algeria in 1962. Although the discussions between President Eisenhower and Mr. Khrushchev at Camp David in September 1959 had seemed to open the door toward further negotiations, the downing of a U.S. U-2 aircraft over Russian territory caused the next summit to abort. The construction of the Berlin wall in 1961 was a further contribution to increased tension.
The Allies' response to the deterioration of the Berlin situation was an increased allied solidarity and the creation of an Allied Mobile Force (AMF) from units supplied by six different countries. It consisted of a land element of five battalions and an air element of four fighter-bomber attack squadrons.
The size of the force may not have been as impressive as its political meaning was and still is. It was the image of the Allies' resolve, to face together any aggression, which the deployment of the AMF to a crisis area might well have demonstrated. Five out of the seven areas identified for possible deployment of the AMF were in the Southern Region.
The end of 1963 was marked by serious disorder among the Greek and Turkish communities in Cyprus. The NATO Council made every effort to preserve friendship between the two members of the Alliance. In March 1964, the United Nations decided to send a peacekeeping force to the island. In August Greece withdrew its personnel from NATO Headquarters in Izmir. Another Mediterranean island was also a focus of attention in the region. On 21 September 1964, Malta gained independence from the U.K., bringing into question the status of the AFMED headquarters on the island. The continued legal status of the installation was solved over a year later, in a joint statement of the NATO Council and the government of Malta.