Однако отпустили Константина Матвеевича Шуйского не просто так. Все те же Колышкин, Козлов и другие с началом войны обратились к наркому ВМФ Кузнецову с просьбой вернуть опытного офицера-подводника на флот. Вслед за Шуйским переслали и его личное дело с многозначительным примечанием «с последующим отбытием срока заключения после войны». Впрочем, для того, чтобы исполнить это предписание, надо было еще остаться в живых.
Вначале Шуйского назначили старпомом подлодки К-3, которой командовал К. Малофеев. Командиром назначать его было нельзя, так как судимость еще не была снята. На К-3 Шуйский участвовал в четырех боевых походах, в которых были потоплены 2 транспорта и поврежден один корабль.
При этом судимость с Шуйского сняли только в 1942 году. Причиной к снятию послужили итоги знаменитого декабрьского боя в 1941 году К-3, которую вывел в море Магомет Гаджиев. Шуйский был в этом походе старпомом. Тогда подводная лодка потопила транспорт, подверглась преследованию, всплыла в надводное положение и расстреляла преследовавшие ее корабли охранения конвоя. В итоге орденами и медалями наградили весь экипаж, кроме одного человека – Шуйского: с него сняли судимость.
Вот как описывает события, которые изменили судьбу старпома К-3, историк Северного флота и писатель-маринист Сергей Ковалев: «19 февраля 1942 года подводная лодка Щ-403, которой командовал капитан-лейтенант Семен Коваленко, высадив на вражеский берег группу разведчиков, ночью в надводном положении выходила из Порсангер-фьорда. Внезапно она встретила немецкий отряд боевых кораблей в составе минного заградителя “Бруммер” и двух тральщиков, М-1502 и М-1503. На “щуке” вахтенный офицер, находившийся в рубке на командирском мостике, растерялся и вместо того, чтобы скомандовать: “Срочное погружение!”, пригласил командира на мостик. Коваленко, поднявшись из прочного корпуса наверх, мгновенно оценил обстановку: лодку обнаружили, а один из тральщиков уже пытается выйти на таран. Расстояние между ним и Щ-403 резко сокращается, и о погружении, даже самом срочном, уже не может быть и речи. Более того, по лодке вражеские корабли открыли ураганный артиллерийский и пулеметный огонь. Командир “щуки” дал команду приготовить кормовые торпедные аппараты к залпу. И аппараты приготовили к стрельбе. Но в тот момент, когда уже нужно было выстрелить по минному заградителю, команда на залп до кормового отсека почему-то не дошла. Однако лодка все равно уклонилась от таранного удара тральщика. Вслед за ним в атаку на “щуку” вышел уже минный заградитель. Но командир прикинул по расстоянию до “Бруммера”, что “по-срочному” они погрузиться успеют.