12—19 января 1938 года в Москве состоялась 1-я сессия Верховного Совета СССР. После уничижительной критики наркома юстиции СССР Н. В. Крыленко, прозвучавшей в речи депутата Багирова, всем стало ясно, что судьба Николая Васильевича предрешена. 19 января на третьем, заключительном совместном заседании Совета Союза и Совета Национальностей (председательствовал на нем А. А. Андреев) с речью об образовании Правительства СССР выступил В. М. Молотов. Перечисляя состав нового Советского правительства, он просил депутатов утвердить народным комиссаром юстиции СССР Николая Михайловича Рычкова.

В августе 1938 года состоялась 2-я сессия Верховного Совета СССР, рассмотревшая целый ряд важнейших законопроектов. Народный комиссар юстиции Н. М. Рычков выступил на этой сессии с докладом «О проекте Положения о судоустройстве СССР, союзных и автономных республик».

В период своей работы в Народном комиссариате юстиции СССР Н. М. Рычков совместно с Прокурором Союза ССР подписал целый ряд приказов, направленных на усиление борьбы с преступностью, которые свидетельствуют о чрезвычайной жесткости проводимой тогда политики. Так, в июле 1940 года совместно с М. И. Панкратьевым он направил на места приказ, в соответствии с которым рабочие и служащие, допустившие опоздания без уважительных причин, более чем на 20 минут после обеденного перерыва или самовольный уход с работы раньше, чем за 20 минут до обеденного перерыва, подлежали привлечению к уголовной ответственности, как за прогул (по части 2 статьи 5 Указа Президиума Верховного Совета СССР от 26 июня 1940 года).

Необходимо заметить, что спрос с работников органов прокуратуры и юстиции, а также судей за неукоснительное выполнение приказов был самый строгий. Любые послабления в карательной практике могли повлечь за собой не только отрешение «провинившегося» от занимаемой должности, но и предание его суду. В августе 1940 года коллегия Наркомюста СССР под председательством Рычкова дважды рассматривала вопросы применения указа от 26 июня 1940 года. Несколько судей, проявивших либерализм в отношении «прогульщиков», сами были отданы под суд. Был уволен и нарком юстиции Белорусской ССР, который отказался привлекать к ответственности за прогулы временных и сезонных работников, полагая, что действие указа распространяется только на лиц, постоянно работающих на производстве. Рычков строго предупредил также наркомов юстиции Украины, Узбекистана и Азербайджана.

Особенно напряженно пришлось работать наркому юстиции СССР Н. М. Рычкову в период Великой Отечественной войны. Он направил на места множество указаний и приказов, обращая особое внимание на наведение порядка с исполнением судебных решений, необходимость чуткого отношения к обращениям военнослужащих и членов их семей и т. п. В экстренном порядке был подготовлен сборник законодательных актов о пособиях, пенсиях и льготах семьям военнослужащих рядового и начальствующего состава. В одном из своих приказов (от 29 июня 1941 года) Н. М. Рычков отмечал, что в эти трудные для всей страны дни «прямым преступлением является волокита, бюрократизм при рассмотрении уголовных и гражданских дел». В другом приказе он обращал внимание на то, что «ни на один день ни один участок народного суда не должен оставаться без народного судьи». Начальники управлений Наркомюста и наркомы юстиции союзных республик должны были лично «ежедневно и ежечасно» решать вопросы укомплектования судов.

Пост наркома (а с 1946 года — министра) юстиции СССР Н. М. Рычков занимал 10 лет. За это время он дважды был награжден орденом Ленина (3 ноября 1944 года и 26 марта 1945 года), а 23 февраля 1945 года — орденом Красного Знамени (второй такой же орден он получил в 1950 году). Был избран депутатом Верховного Совета РСФСР 1-го созыва (в апреле 1938 года) и депутатом Верховного Совета СССР 2-го созыва (в феврале 1946 года). 28 августа 1944 года ему присвоили воинское звание генерал-лейтенанта юстиции.

«Придирки» к Н. М. Рычкову начались сразу же после окончания Великой Отечественной войны. Вначале он получил выговор от Секретариата ЦК ВКП(б) за то, что без предварительного согласования с ЦК партии назначал на должности председателей военных трибуналов. В декабре 1946 года заместитель начальника управления кадров ЦК ВКП(б) Никитин и заместитель заведующего отделом этого же управления Бакакин направили большую записку на имя секретаря ЦК ВКП(б) А. А. Кузнецова «О неправильном стиле руководства министра юстиции Союза ССР тов. Рычкова Н. М.» В ней Николай Михайлович обвинялся чуть ли не в полном развале всей работы Министерства юстиции СССР. На него взваливалась также ответственность и за создание «специальных судов» (их было тогда в стране 887), которые по своей численности уже стояли на втором месте после народных судов, и за нарушения, допускавшиеся судьями и т. п.

Авторы записки делали следующий вывод: «Считаем, что т. Рычкова в интересах дела надо очень серьезно предупредить, иначе он, а вместе с ним и Министерство юстиции СССР и его органы на местах по-прежнему будут не выполнять те требования, которые к ним предъявляются Партией и Правительством». Предлагалось вызвать Н. М. Рычкова на беседу в ЦК ВКП(б), и приобщить записку к его личному делу. Вскоре к служебным неурядицам добавились и личные. Комитет партийного контроля при ЦК ВКП(б) объявил ему выговор за незаконное расходование на строительство личной дачи денежных средств и стройматериалов, принадлежащих министерству.

29 января 1948 года в соответствии с решением ЦК ВКП(б) Верховный Совет СССР освободил Н. М. Рычкова от должности министра юстиции СССР. До декабря того же года он находился в резерве Главного управления кадров, так как подходящей должности для него не оказалось. В конце 1948 года Генеральный прокурор Союза ССР Г. Н. Сафонов предложил Н. М. Рычкову должность заместителя военного прокурора Сухопутных войск. Соответствующее ходатайство, с которым он обратился в ЦК ВКП(б), административный отдел поддержал. Н. М. Рычков снова вернулся в лоно военной прокуратуры. Спустя полтора года, в апреле 1950 года, Г. Н. Сафонов выдвинул Николая Михайловича на впервые вводимую в Главной военной прокуратуре должность начальника 3-го управления (по судебному надзору), а в апреле 1951 года назначил его заместителем Главного военного прокурора.