Они вновь встретились сразу после войны. Щелоков служил ответственным секретарем партийной комиссии политуправления Прикарпатского военного округа, ведал приемом в партию и персональными делами. Начальником политуправления округа был генерал-майор Брежнев. В августе 1946 года демобилизованный Щелоков начал работать на Украине. В 1951 году его перебросили в соседнюю Молдавию и назначили первым заместителем председателя Совета министров республики. В Кишиневе Николай Анисимович вновь трудился под руководством Леонида Ильича, который был первым секретарем республиканского ЦК в 1950–1952 годах.

Брежнев в Кишиневе не задержался. А Николай Анисимович остался в Молдавии. Когда страну возглавил Брежнев, Николай Анисимович получил первое за пятнадцать лет и принципиально важное повышение. Леонид Ильич перевел его с хозяйственной на партийную работу: в марте 1966 года Щелоков приступил к обязанностям второго секретаря ЦК компартии Молдавии. Но пробыл на этой должности всего несколько месяцев. Брежнев забрал его в Москву и назначил союзным министром охраны общественного порядка.

Леонид Ильич окружал себя командой проверенных и преданных ему лично людей. Но решения в политбюро принимались только единогласно. А против назначения Щелокова министром решительно возражали член политбюро, секретарь ЦК Александр Шелепин и его соратники. Однако Брежнев сумел настоять на своем. В сентябре 1966 года Николай Щелоков был назначен министром охраны общественного порядка СССР. Он всегда помнил, что своей карьерой обязан Леониду Ильичу. После переименования министерства, 25 ноября 1968 года, Щелоков стал министром внутренних дел.

Щелоков принял органы внутренних дел в бедственном положении — катастрофически не хватало профессионалов. Люди не шли в МВД: мешали низкие зарплаты и непрестижность службы.

«Я рассказал Николаю Анисимовичу, — вспоминал генерал милиции Олег Иванович Морозов, занимавшийся в министерстве кадрами, — в каких тяжких условиях живут молодые сотрудники. Зарплата не превышает шестидесяти рублей в месяц. В общежитиях не хватает мест, некоторые милиционеры спят по очереди или на двухъярусных койках. Не в лучшем положении находятся и молодые офицеры».

Министерство внутренних дел — это настоящая империя. В нее входили четыре с половиной тысячи городских и районных отделов внутренних дел. Не так-то просто руководить такой махиной, заставить ее слушаться. Щелокову это удалось. Более того, в министерстве Щелокова даже любили, а ветераны и по сей день говорят, что он был лучшим министром за всю историю ведомства. Николай Анисимович никого не прижимал, давал людям волю. Зарплату увеличил и добился, чтобы за звание офицерам милиции платили столько же, сколько и офицерам Вооруженных сил.

«То, что не могли сделать его предшественники, сделал он, — вспоминал бывший начальник уголовного розыска страны профессор Игорь Иванович Карпец. — Могут сказать: что ж тут особенного, он же “выходил прямо на Брежнева”. На это можно ответить: “выходили” на Брежнева многие, однако преимущественно для себя, Щелоков же, не забывая себя, много сделал для министерства».

Деятельность Щелокова в МВД складывалась из двух этапов. На первом Николай Анисимович очень серьезно отнесся к новому делу. Он пытался устроить работу правоохранительных органов на современный лад и не отвергал с порога иностранный опыт, понимая, что у западных стран есть чему поучиться. На втором этапе он только наслаждался высокой должностью и занимался устройством своего быта, в чем весьма преуспел.

Щелоков пытался модернизировать доставшееся ему ведомство. Он прислушивался к профессионалам, способным предложить новые и прогрессивные идеи. Он хотел, чтобы в криминалистике учитывались последние достижения науки. При нем появилась новая спецтехника, так называемые «чемоданчики следователя», которые позволяли квалифицированно проводить осмотр места преступления.

Он создал Штаб МВД. В штабе появился организационно-аналитический отдел, который занимался анализом преступности в стране и искал научно обоснованные пути борьбы с ней. Николай Анисимович был человеком доступным и открытым, поддерживал и продвигал профессионалов, тех, кто способен был предложить новые и неожиданные идеи. Питал слабость к людям с научными степенями. Его любимцем и ближайшим сотрудником был начальник штаба министерства генерал Сергей Михайлович Крылов. Щелоков в нем души не чаял.

— Тот, кто рекомендовал министру Крылова, — рассказывал генерал Владимир Статкус, бывший заместитель начальника следственного управления МВД, — оказал Щелокову огромную услугу. Человек огромной энергии, Крылов умел пробивать свои идеи и собирать вокруг себя единомышленников.

Сергей Крылов привел в министерство молодых и талантливых людей, они генерировали идеи, которые министр с удовольствием поддерживал.

— Крылов хотел изменить милицию, — вспоминал обозреватель журнала «Милиция» Генарий Попов. — Я думаю, министр и Крылов совпали в желании сделать милицию нормальной, доброй, интеллигентной…

Научно-исследовательский институт МВД выписывал все полицейские журналы, которые выходят в мире, покупал иностранные книги и изучал работу полиции за рубежом, особенно оперативно-розыскную деятельность. Щелокову переводили книги о полиции в разных странах, и он их читал. Зарубежный опыт, правда, не всегда полезен. Скажем, милицию еще при прежнем министре вооружили резиновыми дубинками. Щелоков откровенно говорил, что палка легализовала в милиции битье.

В министерстве первыми заинтересовались полиграфом — детектором лжи. В 1968 году он прошел испытания на Петровке. Но в ЦК эксперименты с детектором лжи как буржуазной выдумкой сочли опасными. Все прекратилось. Пионер этого дела кандидат биологических наук Валерий Алексеевич Варламов, создатель первого в нашей стране перьевого детектора лжи, был уволен из НИИ МВД.

Щелокову объяснили пользу профилактики преступлений и смягчения наказаний. И теперь уже он сам объяснял партийным руководителям, что нельзя сурово наказывать за незначительные проступки — избыточная жестокость плодит новых преступников. Министр создал управление профилактики, которое опекало прежде всего тех, кто вышел на свободу. Им помогали найти работу. Николай Анисимович понимал, что осужденные — тоже люди. И в тюрьме они не навсегда. Кому будет лучше, если они вернутся из мест заключения озлобленными и ненавидящими всех и вся?

— Николай Анисимович, побывав в следственном изоляторе, был крайне удручен, — вспоминал генерал Василий Игнатов, бывший министр внутренних дел Чувашии. — Увидел параши, распорядился провести канализацию. Говорил: «Что же мы заключенных за скотов держим?»

Места заключения были очень старыми. Новые не строили. Раз в программе партии сказано, что в Советском Союзе преступность скоро будет искоренена, зачем строить тюрьмы?

Щелоков пытался уговорить политбюро разрешить ему вступить в Интерпол, но не уговорил. Интерпол считался идеологически чуждой организацией.

«Одно его качество оставалось неизменным, — вспоминал профессор Карпец. — Как бы его отношения с тем или иным человеком ни портились, он не позволял себе расправиться с ним, он всегда находил какую-то возможность, грубо говоря, не добивать человека до конца, прощая подчас немалые прегрешения. Чем это объяснить? Может быть, тем, что он сам был не безгрешен? Может быть. Но, вероятно, и тем, что он в общем-то был по характеру не злобный человек».