Заложена 3 июля 1961 года на стапеле цеха № 42 Северного машиностроительного предприятия. Спущена на воду 5 июля 1962 года. С 6 июля по 14 сентября 1962 года на лодке были проведены швартовные испытания оборудования и механизмов. Заводские ходовые испытания проводились в период с 14 по 25 сентября 1962 года. Государственные испытания проходили с 26 сентября по 29 октября 1962 года. 29 октября 1962 года Государственная комиссия подписала акт о завершении государственных испытаний корабля.
Включена в состав Северного флота 14 ноября 1962 года, зачислена в состав 3-й дивизии подводных лодок с местом базирования в Западной Лице. Первым командиром К-133 был назначен капитан 2-го ранга Слюсарев Георгий Алексеевич.
В учебном походе 17 августа 1963 года в подводном положении произошла авария главной энергетической установки (ГЭУ) левого борта с выходом её из строя и повышением радиоактивного фона. В течение 38 часов силами экипажа нештатная ситуация устранена, лодка продолжила выполнение учебного похода силами ГЭУ правого борта[2].
В 1963 году К-133 совершила первый в истории ВМФ СССР поход в экваториальную Атлантику. Продолжительность похода составила 51 сутки.
В период с 2 февраля по 26 марта 1966 года К-133 совместно с ПЛАРК К-116 впервые в мире совершила переход с Северного флота на Тихоокеанский флот южным маршрутом через пролив Дрейка без всплытия. Командовал переходом командующий 1-й флотилии подводных лодок контр-адмирал Сорокин А. И., командиром К-133 был капитан 2 ранга Столяров Л. Н. При переходе лодка прошла 21000 морских миль за 52 суток. Указом Президиума Верховного Совета СССР от 23 мая 1966 года за образцовое выполнение задания командования и проявленное при этом мужество и героизм командиру АПЛ капитану второго ранга Столярову Л. Н., руководителю перехода, контр-адмиралу Сорокину А. И., замполиту ПЛА «К-133» капитану второго ранга Усенко Н. В., флагманскому инженер-механику Морозову И. Ф. были присвоены звания Героев Советского Союза.
14 апреля 1966 года за успешное выполнение задания К-133 было присвоено почётное звание гвардейская.