Заложена 1 августа 1939 года на заводе № 112 (Красное Сормово) в Горьком под стапельным номером 272. Спущена на воду 25 августа (по другим данным 24 августа) 1940 года. К началу войны техническая готовность корабля составляла 72%. Осенью 1941 года подводная лодка отбуксирована в затон в районе Камышина, но весной 1942 года переведена на Каспий для достройки и прохождения сдаточных испытаний на завод № 638 (завод имени Сталина) в Астрахань. В ноябре 1942 года командиром корабля назначен капитан 2 ранга Векке Виктор Кузьмич. 20 февраля 1944 года вступила в строй и вошла в состав Каспийской флотилии.

    15 марта 1944 года субмарина вышла из Баку в составе Отдельного дивизиона ПЛ и 20 мая прибыла в Молотовск (ныне Северодвинск). В этот же день субмарина зачислена в состав Северного флота. Еще 24 апреля приказом Наркома ВМФ корабль получил имя «Герой Советского Союза Нурсеитов». 13 июня командиром «С-16» назначен капитан 3 ранга Лепёшкин Алексей Васильевич, а 15 июля 1944 года она вошла в состав Учебного дивизиона ПЛ СФ. 16 сентября подводная лодка зачислена в состав 2-го дивизиона бригады ПЛ СФ и 19 октября прибыла в Полярное.

    7 ноября 1944 года «С-16» вышла на позицию в район между Тана-фьордом и Нордкапом (сектор «С»). Первый боевой поход подводной лодки обеспечивал командир 2-го дивизиона капитан 2 ранга И.Ф. Кучеренко. Утром 8 ноября субмарина заняла указанный район, но в ночь на 10 ноября подводная лодка по приказу командования перешла в район мыса Нордкин, где днем 10 ноября из-за большого курсового угла не смогла атаковать конвой. 12 ноября субмарина перешла в устье Порсангер-фьорда, но 19 ноября «С-16» прервала поход и направилась в базу. На подводной лодке лопнул змеевик компрессора воздуха высокого давления. Утром 21 ноября «С-16» прибыла в Полярное.

    Так как конечной точкой немецких коммуникаций в октябре 1944 года стал Тормсё, который находился в зоне оперативной ответственности союзников, выход ПЛ СФ на позиции вскоре был прекращен.

    После окончания войны подводная лодка служила на Севере. 29 декабря 1955 года «С-16» была выведена из боевого состава, разоружена и переформирована в плавучую зарядовую станцию «ПЗС-28» (с 27 декабря 1956 года «ЗАС-3»), а 12 марта 1958 года исключена из списков ВМФ, расформирована и сдана на слом. Корпус подводной лодки разобран на металл в Мурманске.