By 1966 the Soviets had built up their Mediterranean force an average daily strength of fifteen ships which were making port calls from Egypt to Gibraltar. This initial Soviet deployment in the eastern Mediterranean was to counter the American deployment SSBNs there. As American ballistic submarines improved in range and accuracy, the Soviets were drawn into blue water operations to hunt and destroy these boats. Naval air cover was necessary for the surface fleets to performs these tasks, and all of the USSR’s surface units for deploying air power at sea would be built in the Black Sea.
. The first significant appearance of Soviet sea power in the Mediterranean came in 1967 during the Arab-Israeli conflict. During the Six-Day War (June 1967) the Soviets increased their force in a show of support for the Arab states. That was the first opportunity taken by the Soviets to demonstrate their willingness to influence major events in the area by the use of military power. During that crisis the Soviet Mediterranean Squadron numbered up to some 70 units, some of which were in Port Said and Alexandria, to prevent Israeli attacks against those ports.
The cold war was getting even colder. The invasion of Czechoslovakia in August 1968 contributed to the lowering temperature. For the Mediterranean it was the prelude to Albania renouncing its membership of the Warsaw Pact. Late that year, the MARAIRMED Command was activated in Naples to improve NATO surveillance in the Mediterranean. The Alliance's concern for the never ending Soviet penetration, by any means, in the Mediterranean basin was reflected in this recognised need for increased vigilance. NATO ministers instructed the Council in permanent session to keep the situation under close review. In the framework of measures studied at Reykjavik meeting the previous June, the NATO Defence Planning Committee approved, in May 1969, the future establishment of a Naval On-Call Force Mediterranean. This maritime force, like the AMF for land and air, was to play an important deterrent role by showing the Allies' solidarity and their determination to put their forces under one flag. Assigned to NAVSOUTH, the On-Call force was activated 43 times in 1970-1991, when it was decided to replace it with a permanent force. It initially comprised up to five frigates or destroyers.
This Soviet presence rapidly expanded, and by 1970, the eskadra maintained nearly 70 vessels in the eastern Mediterranean, with logistical support coming from the Black Sea. During the Yom Kippur War (October 1973) the force rose from 52 to 95 ships [other estimates placed the increase at from 60 to 84 ships] - including over a dozen destroyers and nearly two dozen submarines - outnumbering the American 6th Fleet. During another peak period, the squadron sent 62 ships with 18,720 personnel into the Mediterranean.
In the late 1980s the political and socio-economic landscape surrounding the Mediterranean area changed. Popular demonstrations in Bulgaria and Romania led to dramatic regime changes. Hungary opened its western borders. The Berlin Wall came down. NATO offered new relationships to Central and Eastern European nations. The Warsaw Pact ceased to exist on 31 March 1991, and the Mediterranean Eskadra effectively withdrew from the Mediterranean.
In January 1996 the Russian aircraft carrier Adm. Kuznetsov deployed in the Mediterranean to show the flag and help commemorate the Russian Navy's 300th anniversary. The Russian navy RNS Admiral Kuznetsov (CV 063) battle group, on its maiden Mediterranean deployment, was accompanied by guided missile cruisers, RNS Sovremenny, RNS Besstrashny, RNS Pylky, and supporting auxiliary ships. This marked the first significant deployment of Russian warships to the Mediterranean in five years. Elements of the US Navy's America (CV 66) carrier battle group and Wasp (LHD 1) amphibious ready group conducted bilateral operations with the Russian carrier battle group whiel it was in the Mediterranean.During the Yugoslav crisis, Russian warships were readied to sail to the Mediterranean. On 30 March 1999, following the outbreak of the Kosovo War, Russia announced plans to send a flotilla of up to eight war ships into the Mediterranean. Defense Minister Igor Sergeyev stated that a decision on when to deploy them had not been made, and the Russian government indicated it did not intend to become entangled in the conflict in the Balkans. In response, US State Department spokesman James Rubin said Washington wass "obviously concerned by the signal such a large deployment might send to Belgrade and the other countries in the region." At least seven anti-submarine and missile-carrying frigates, reconnaissance and escort ships from the Black Sea fleet, based in Sevastapol, were repotedly ready to deploy at the beginning of April 1999, but no order came. The flotilla, reportedly consisting of one cruiser, two destroyers, two patrol ships and three support ships, was said to include the destroyer Admiral Golovko, the anti-submarine ships Kerch and Sderzhanny, and the patrol ships Pytlivy and Ladny. The Liman reconnaissance ship, sailed out of the Black Sea on 04 April 2000, and into the Adriatic, where it monitored NATO military operations against Serbia. Subsequently, Russia notified Turkey through diplomatic channels of plans for passage of the straits by the Russian task force between April 15 and 22, though in fact this deployment did not occur. In early July 1999 five Russian landing ships took paratroopers from the Tula and Pskov airborne divisions to the Balkans to join Russia's peacekeeping force in Kosovo. The five ships were: Azov, Cesar Kunikov (Ropucha class), #69, #150, #156 [probably Polnochny-class ].
On 23 November 1999 Prime Minister Vladimir Putin announced to the Russian Security Council that Russian Navy operations would soon extend beyond their previouly limited boundaries. Areas mentioned in his speech as having strategic significance for Russia were the Baltic Sea and regions to the south of Russia. Putin stated that additional funds would be provided for deployment by November 2000 in the Mediterranean of Russia's sole aircraft carrier, the Admiral Kuznetsov, a destroyer, a frigate, one tanker, and nuclear-powered submarines carrying SLBMs. The Tartus base in Syria, first used for Russia's Mediterranean squadron in 1983, was also to be reactivated.