Since 1952, AFSOUTH had been composed of an integrated staff from six nations: France, Greece, Italy, Turkey, the United Kingdom and United States. A change became necessary after an official announcement was made by the French government on 29 March 1966: French personnel would withdraw from the NATO integrated military structure, assignment of French forces to international Commands would terminate and all the NATO or allied units or installations would be transferred from French territory by 1 April 1967. The NATO Council, therefore, had to make appropriate modifications to the Allied organisation. As France continued to be a member of the Alliance, a new forum was established to discuss military questions in which France would not participate: the Defence Planning Committee. SHAPE Headquarters was transferred to Belgium, along with the NATO Headquarters. The Central European Command was hosted by the Netherlands, with a German commander, while Italy was asked to provide a new home for the NATO Defence College.
France's withdrawal from the integrated military structure was yet another factor leading to a reorganisation of AFSOUTH. The overall picture of the Mediterranean was totally different from the one which had framed Adm. Carney's efforts. Western influence over the African littoral countries had dramatically decreased. Western forces which had been present in some of these countries had been withdrawn. The political orientation of some littoral countries had shifted towards the left. As a result of the French withdrawal from the integrated military structure of the Alliance, the Southern Region had lost the use of the NATO naval installations at Toulon and Mers-el-Kebir. All these changes occurred just while the Soviets were succeeding in politically and militarily penetrating into the Mediterranean area.
The first permanent deployment of Soviet naval units to the Mediterranean dates from 1964, when four or five units started to show the red flag on this sea. This presence rapidly grew to a level of 40 to 50 units during the following years. At the same time, the Soviets increased their effort to influence the entire area; linking themselves to some littoral countries either through co-operation treaties, or by large-scale sales of military equipment.
NATO military planners were well aware that the allied military structure in the southern flank was no longer adequate to face either the increased threat or the new political and military situation in the Mediterranean basin. In addition, the two Major Commands in the area had overlapping responsibilities. AFSOUTH was responsible for the critical southeastern maritime zone where adjacent land and air operations were under its subordinate commands - LANDSOUTHEAST and 6ATAF. In the same area, naval operations were conducted by commands subordinated to AFMED. Another problem was the proliferation of subordinate commands which increased the need for effective co-ordination.
It was not until 1965 that the Military Committee agreed to the following proposals made by SACEUR on the command structure and boundaries in Southern Europe and in the Mediterranean/Black Sea area:
- Disestablishment of AFMED Headquarters.
- Reestablishment of the Headquarters Allied Naval Forces Southern Europe (NAVSOUTH) under an Italian Adm.
- Reorganisation of the areas assigned to the subordinate commands (i.e. the command boundary between the Eastern and Central Mediterranean area was modified in order to coincide with that of 5ATAF and 6ATAF).
- Redesignation of the maritime U.S. Fleet Air Wing Mediterranean (U.S.FAIRWINGMED) command as Maritime Air Forces Mediterranean, to assume responsibility for all assigned maritime patrol aircraft in the Mediterranean. An international staff was to be assigned to this new allied headquarters, to be activated in Naples.Designation of the U.S. Commander Submarine Flotilla 8 as Commander, Submarines Mediterranean (COMSUBMED), in addition to his wartime responsibilities as Commander Task Force 442 (CTF 442); and the establishment of an international staff for this command to be co-located with the U.S. staff in Naples.
AFMED was deactivated on 5 June 1967. AFSOUTH became the only Major Subordinate Command in the South. NAVSOUTH was reactivated on the same date, in Malta; and the Commander, Adm. Luciano Sotgiu, Italian Navy, became a principal subordinate commander to AFSOUTH. By the following August, the NATO Defence Planning Committee had approved the reorganisation of the Southern European Command, as proposed by the Military Committee. However, by the time the bureaucratic procedure put into effect the original proposals of 1965, new changes affected the military posture in the area. In addition to the announced withdrawal of French forces from the integrated military structure, the United Kingdom decided to reduce her military presence in the area. And, on Libyan request, the U.S. agreed to withdraw its forces from the important air base of Wheelus Field. The very day AFMED was deactivated, the long-simmering Arab-Israeli conflict sparked a major crisis in countries bordering on its area of responsibility: the "Six Day War."