Known in the West by their NATO reporting name as the Juliett class, the Project 651 diesel-electric submarines were designed in the 1950s to provide the Soviet Navy with a nuclear strike capability against the east coast of the United States. They carried four nuclear cruise missiles, which could be launched while the submarine was surfaced and moving less than four knots (7 km/h). Once surfaced, the first missile could be launched in about five minutes; subsequent missiles would follow within about ten seconds each. Initially, the missiles were the inertially-guided P-5 (NATO reporting name SS-N-3 Shaddock). When submarine-launched ballistic missiles rendered the P-5s obsolescent, they were replaced with the P-6 (also NATO reporting name SS-N-3 Shaddock, though it is a very different missile) and the P-500 4K-80 "Bazalt" (SS-N-12 Sandbox) anti-ship cruise missiles designed to attack American aircraft carriers. A special 10m2 target guidance radar was built into the forward edge of the sail structure, which opened by rotating. The boats were eventually fitted with the Kasatka satellite downlink for targeting information.

The Juliett class had a low magnetic signature austenitic steel double hull, covered by two inch (50 mm) thick black tiles made of sound-absorbing hard rubber. They had exceptionally high reserve buoyancy, and were divided into eight watertight compartments:

the forward torpedo room
living accommodations for officers and chiefs and the forward batteries
the missile control room and batteries
the control room
crew berthing and batteries
the forward engine room containing the diesels and generators
the aft engine room with the electric motors
the aft torpedo room.

Initial plans called for 35 submarines of this class. In fact only 16 were actually built, most by Krasnoye Sormovo shipyard in Gorky. They were commissioned between 1962 and 1968, and served through the 1980s. The last one was decommissioned in 1994.

Submarine K-67 was laid down at the Krasnoe Sormovo named after A.A.Zhdanov, Gorky (yard No.524) on 31 January 1965, launched on 29 October 1966, and commissioned on 30 September 1967 into the Northern Fleet.

On 25 July 1977 renamed to B-67, and on 25 September 1981 she transferred to the Black Sea Fleet.

Decomissioned on 30 June 1993.

In 1995, the submarine was cut into metal in Inkerman.