Stępkę okrętu położono 12 stycznia 1956 roku w Stoczni Bałtyckiej im. S. Ordżonikidze (SS3. Nr 189) w Leningradzie, 18 maja został zarejestrowany na liście Marynarki Wojennej ZSRR, a 16 listopada zwodowano go pod nazwą S-363. przeszedł wiosną 1957 roku w Mołotowsku, a 17 września rozpoczął służbę. Wyróżnił się w ćwiczeniach torpedowych w 1958 roku. Od 20 sierpnia 1966 roku przeniesiony do Floty Bałtyckiej. W latach 1967–1968 przechodził remont w Kronsztadzie, a w latach 1979–1981 w stoczni SR3-29 Tosmar w Libawie.
Incydent thumb|Widok na Gåsefjärden od strony północnej W 1981 roku S-363 uległ dwóm wypadkom. Pierwsza kolizja – z trałem statku rybackiego – miała miejsce 18 października w rejonie na wschód od Bornholmu i spowodowała uszkodzenie radiopelengatora na jednostce. Poważniejsze reperkusje miał incydent z 27 października, kiedy to o godz. 21.57 uderzył w podwodną skałę na wodach terytorialnych Szwecji około 6,2 Mm (10 km) od Karlskrony i został wyrzucony na powierzchnię. Obecność okrętu podwodnego wiązała się z odbywanymi w tym rejonie manewrami floty szwedzkiej, testującej nowe typy uzbrojenia. Marynarka szwedzka zareagowała na to jawne naruszenie suwerenności spokojnie, wysyłając na radziecki okręt nieuzbrojonego oficera, który zażądał wyjaśnień od dowódcy.