Работы по проектированию первой советской атомной субмарины начались после выхода постановления Совмина СССР №-4098-1616 от от 9 сентября 1952 «О проектировании и строительстве объекта 627». Главным конструктор первой атомной субмарины был назначен Владимир Николаевич Перегудов. Руководителем работ с 1953 года стал учёный-кораблестроитель Сергей Александрович Базилевский. При этом в процессе проектирования с 1952 года разрабатывалось два варианта — вариант с водо-водяным реактором и реактором с жидкометаллическим теплоносителем. К-3 стало воплощением варианта с водо-водяным реактором, а альтернативный проект был создан позже под индексом К-27, учеником А. К. Назаровым в корпусе этого проекта.
К-3 была заложена 24 сентября 1955 года в Северодвинске, на заводе № 402 (ныне «Севмаш»), заводской № 254. В августе 1955 года командиром лодки был назначен капитан 1-го ранга Л. Г. Осипенко.
Реакторы пущены в сентябре 1957 года, спущена на воду 9 октября 1957 года. 15 июня 1958 года К-3 вступила в строй, а 4 июля 1958 года лодка впервые дала ход под атомной силовой установкой, 17 декабря 1958 года принята у промышленности под гарантию устранения недостатков.
Параллельно, с заметным отставанием, проектировалась и строилась требуемая для поддержки АПЛ новая береговая инфраструктура.
12 марта 1959 года К-3 вошла в состав 206-й отдельной БрПЛ с базированием на Северодвинск.
В июле 1962 года впервые в истории Советского Военно-Морского Флота она совершила длительный поход подо льдами Северного Ледовитого океана, во время которого дважды прошла точку Северного полюса. Под командованием Льва Михайловича Жильцова 17 июля 1962 года впервые в истории советского подводного флота всплыла около Северного полюса. Экипаж корабля недалеко от полюса во льдах Центральной Арктики водрузил Государственный флаг СССР. После возвращения в базу в Йоканьге, лодку на пирсе встречали Н. С. Хрущёв и министр обороны Р. Я. Малиновский. Руководителю похода контр-адмиралу А. И. Петелину, командиру корабля капитану 2 ранга Л. М. Жильцову и командиру БЧ-5 (силовая установка) капитану 2 ранга инженеру Р. А. Тимофееву присвоено звание Героя Советского Союза. Весь личный состав корабля был награжден орденами и медалями.
8 сентября 1967 года произошел пожар в I и II отсеках при нахождении на боевом дежурстве в Норвежском море, погибло 39 человек.