Konstrukcja B-67 projektu W611 oparty był na konstrukcji jednostek projektu 611. Dwie wyrzutnie rakietowe systemu D-1 umieszczono w przedłużonym kiosku, zaś w celu zmieszczenia w kadłubie systemu kontroli strzelania rakietowego, z projektu usunięto jedną z czterech grup baterii elektrycznych oraz część przestrzeni załogi, którą przesunięto na miejsce przedziału torpedowego. W rezultacie okręt przenosił jedynie 10 torped w wyrzutniach torpedowych na dziobie i rufie, bez ich dodatkowego zapasu. Przeprowadzona przez biuro CKB-16 pod kierunkiem Nikołaja N. Isanina modyfikacja projektu 611 do projektu W611 spowodowała także usunięcie działa pokładowego oraz spadek prędkości jednostki do 16,5 węzłów w położeniu nawodnym oraz 12,5 węzła pod wodą.
Sekcje okrętu zostały wyprodukowane w Leningradzkim Zakładzie Mechanicznym, po czym zostały przetransportowane do Mołotowska (od 1957 roku Siewierodwińska), a następnie zostały zmontowane w Zakładzie nr 402, gdzie 5 września 1955 roku okręt został zwodowany z numerem taktycznym B-67.