Od początku okręty projektu 651 miały być również przystosowane do przenoszenia nowych pocisków przeciwokrętowych P-6 przeznaczonych do atakowania okrętów nawodnych znajdujących się poza horyzontem za pomocą głowic atomowych lub konwencjonalnych. Wiązało się to z koniecznością uwzględnienia w konstrukcji okrętu podwodnego anten ich systemu kierowania Argumient. Głównym celem nowych pocisków miały być amerykańskie lotniskowce. Do wstępnego wskazywania celów wykorzystywano samoloty rozpoznawcze Tu-95RC. W praktyce pociski strategiczne P-5 nie były na tych okrętach stosowane, a jedynie przeciwokrętowe P-6.
Budowę pierwszego okrętu K-156 rozpoczęto w Zakładzie Bałtyckim w Leningradzie 16 listopada 1960 roku, a wodowano go 31 lipca 1962 roku. Wiosną 1963 roku okręt został przebazowany na daleką północ, gdzie prowadzono próby rakiet. Został oficjalnie wcielony do służby 10 grudnia 1963 roku. Drugi okręt K-85 wszedł do służby w grudniu 1964 roku, a dalsze czternaście, budowane już w zakładach Krasnoje Sormowo, weszły do służby w latach 1965–68. Dwa okręty służyły we Flocie Oceanu Spokojnego, a pozostałe we Flocie Północnej.