[2][3] The ships mounted a primary armament of long-range missiles designed for attacking US Navy carrier battle groups.

The ship carried 1,690 t (1,660 long tons) of fuel oil, which gave a range of 10,500 nautical miles (19,446 km; 12,083 mi) at 14 knots (26 km/h; 16 mph).

[8] For the anti-surface warfare role, Vladivostok was originally intended to mount the P-500 Bazalt (NATO reporting name SS-N-12 'Sandbox') missile, but protracted development meant that instead the same 4K44 missiles (NATO reporting name SS-N-3 'Shaddock') as carried by the Project 58 warships were mounted, although they were launched from two specially designed twin KT-35-1134 P-35 launchers carried midships.

[4] A landing pad and hangar was fitted aft for a ranging Kamov Ka-25T helicopter (NATO reporting name 'Hormone-B') to enable mid-course guidance.

[14] Between January 1980 and March 1983, the ship was upgraded with four six-barrel 30 mm (1 in) AK-630 close-in weapon systems installed near the bridge to improve anti-missile defence.

[16] On commissioning, Vladivostok travelled with the Project 61 ship Strogy and other Soviet vessels on a long tour, via the Black Sea, Lagos in Nigeria, Somalia, the port of Aden in South Yemen and operations in the Indian Ocean from Baltic Sea to the ship's name port of Vladivostok, arriving on 11 February 1970.

[17] Between 10 and 27 August 1971, the vessel, accompanied by Project 58 ship Admiral Fokin and supported by a fleet that included Strogy and Odaryonny, took part in a large exercise in the Pacific Ocean.

The exercise was followed by an investigation of the testing areas used by the United States Navy between the Aleutian Islands and Hawaii, a distance of 13,800 nautical miles (25,600 km; 15,900 mi).

[19] The conflict quickly involved naval vessels, with the Indian Navy sinking the destroyer Khaibar, minesweeper Muhafiz and MV Venus Challenger on 4 December in Operation Trident using Soviet-built P-15 Termit anti-ship missiles.

[22] The threat of further escalation and the intervention of the United States Navy led to the Soviet Union dispatching a substantial fleet to the Indian Ocean.

[23] Vladivostok was dispatched on 13 December, joined Varyag, Strogy and other vessels under the command of Dmitry Pozharsky and remained on station until 6 March the following year.

The ship was made open to the public during April 1972 and, on 30 June, sailed on a tour with Minister of Defence Andrei Grechko, Admiral of the Fleet Sergey Gorshkov and other officials.

[24] The ship closed the 1970s with a tour of the Indian Ocean, visiting allies in Port Louis, Mauritius, Victoria, Seychelles, Maputo, Mozambique, Cam Ranh Bay, Vietnam, the Dahlak Archipelago, which was at that time part of Ethiopia, and Aden, finishing in August 1978.

In between, the ship revisited Beira, Mozambique between 16 and 25 August as a gesture of solidarity with FRELIMO in their war with rebels backed by South Africa.