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 года ему присвоили воинское звание генерал-лейтенанта юстиции.