Budowę jednostki powierzono zakładowi nr 402 w Siewierodwińsku (współcześnie „Siewmasz”), gdzie 16 października 1958 roku rozpoczęto budowę okrętu. K-19 zwodowano 8 kwietnia 1959 roku, jego budowę ukończono zaś 12 listopada 1960 roku. Od samego początku swojego istnienia okręt uważany był za pechowy, co wzięło swój początek od nieudanego rozbicia butelki szampana podczas wodowania, co w świecie marynarzy uważane jest za zwiastujące przyszłe nieszczęścia.
Służba operacyjna Po ukończeniu, wraz z drugą jednostką tego projektu, K-19 został wysłany do bazy Zapadnaja Lica, gdzie 30 kwietnia 1961 roku wszedł do służby we Flocie Północnej i wraz z jednostkami projektu 627A utworzył samodzielną brygadę. Od stycznia 1961 roku brygada ta stanowiła podstawę I Flotylli składającej się z dwóch dywizjonów – 3. tworzonego przez jednostki projektu 627A (NATO: November) oraz 31. złożonego z jednostek projektu 658. 30 grudnia 1963 roku zakończono modernizację okrętu do standardu projektu 658M (NATO: Hotel II) poprzez wymianę systemu rakietowego D-2 na system rakietowy D-4 z pociskami balistycznymi R-21 o większym zasięgu 1400 kilometrów. Instalacja nowego systemu wymagała znacznych zmian konstrukcyjnych okrętu, wynikających z przystosowania systemu D-4 do odpalania pocisków R-21 także spod powierzchni wody. R-21 był pociskiem tzw.