Ochakov was laid down in the Soviet Union on 25 December 1969, launched on 30 April 1971, and commissioned in the Soviet Black Sea Fleet on 4 November 1973. The ship was constructed in the 61 Kommunar Shipyard at Nikolayev (Mykolaiv) on the Black Sea. She was in service with the Soviet Fleet until 1991, and then joined its successor, the Russian Navy. In 2000, the ship was laid up for modification and repairs. By 2006, all work on the ship had been halted, and, in 2008, the ship was towed from Sevmorzavod.[4][5]
On 20 August 2011, the naval flag of Ochakov was hauled down and the ship prepared to be sold for scrap.[6][7]