В структуру нового министерства вошло 7 управлений - милиции, исправительно-трудовых лагерей и колоний, пожарной охраны, службы МПВО, кадров, архивное и хозяйственное, 6 самостоятельных отделов и три других подразделения. Первая коллегия нового министерства собралась 31 мая 1956 года и была посвящена состоянию уголовной преступности в РСФСР. К 1955 году по сравнению с 1954-м преступность в России возросла с 1906 тысяч до 2155 тысяч случаев, или на 13 процентов, а раскрываемость преступлений составила 85,5 процента. Узда, накинутая когда-то Сталиным на общество, после его смерти несколько ослабла, и преступники не преминули этим воспользоваться. Масштабы эпидемии стало принимать уличное хулиганство. По поводу этого явления на коллегии МВД РСФСР звучали заявления о принятии к хулиганствующим элементам усиленных мер общественного воздействия вплоть до предоставления уличным и домовым комитетам права выносить решение о выселении отдельных лиц из города на определенный срок. Преступность наглела, а органы внутренних дел России влачили поистине нищенское существование. Например, на весь 1955 год органам внутренних дел России было выделено лишь 56 легковых автомобилей "ГАЗ-69", а 330 поселковых отделений милиции вообще не имели никаких транспортных средств. В таких крупных городах, как Свердловск, Казань, Хабаровск, Новосибирск, Ярославль, Сталинград, не было ни одного телефонизированного поста милиции.
Тем временем по мере укрепления позиций Н. Хрущева на вершине кремлевского Олимпа приближалась к своему логическому завершению и карьера Сергея Крылова на посту министра внутренних дел Союза.
В 1955 году в нескольких городах СССР прошли открытые судебные процессы над соратниками Л. Берии. В Ленинграде перед лицом Фемиды предстал бывший министр союзного МГБ Виктор Абакумов и несколько сотрудников МГБ, повинных в фабрикации летом 1949 года так называемого "ленинградского дела". В Тбилиси судили группу сподвижников Л. Берии во главе с бывшим министром МГБ Грузии Рухадзе. В Баку на скамье подсудимых оказался бывший первый секретарь ЦК КП Азербайджана Багиров, давний соратник Берии еще по работе в ВЧК Азербайджана. Эти судебные разбирательства привлекли внимание сотен тысяч людей. Общество было буквально потрясено столь откровенными разоблачениями преступных деяний некогда такого могущественного ведомства, каким являлось МГБ. Резонанс от этих процессов достиг и ГУЛАГа. К тому времени реабилитация осужденных, начатая еще в 1953 году, шла очень медленно, а за весь 1954 год из мест заключения домой возвратились только 10 тысяч человек, да и то это были бывшие партийные деятели среднего и высшего эшелонов власти. На остальных амнистия почти не распространилась. В результате в лагерях начались бунты, во главе которых стояли уголовники. Один из таких крупных инцидентов произошел в Норильске на шахте "Капитальная". Заключенным удалось нейтрализовать охрану и отнять у нее оружие. Весть об этом дошла до Москвы, и министр внутренних дел СССР С. Круглов поручил своему заместителю генералу Ивану Масленникову любой ценой подавить восстание. Что было сделано самым безжалостным образом, в результате погибли сотни людей. Точно так же было подавлено и восстание в Кенгире.
Проблема ГУЛАГа вкупе с жестокостью, проявленной С. Кругловым, стала основным козырем Н. Хрущева в борьбе с министром внутренних дел СССР. В конце 1955 года в МВД СССР состоялась коллегия министерства, на которой было отмечено: в руководстве министерством допускалась порочная практика, когда в решении крупных, имеющих государственное значение вопросов нарушался принцип коллективного руководства, не учитывалось мнение членов коллегии и руководителей местных органов. Относительно самого министра внутренних дел коллегия отметила, что он не принял во внимание правильные замечания отдельных руководящих работников министерства, указывавших на необходимость установления ограничений при освобождении из лагерей некоторых категорий преступников.
14 - 25 февраля 1956 года в Москве проходил XX съезд КПСС, на котором Н. Хрущев выступил со своим эпохальным докладом "О преодолении культа личности и его последствий". Хрущев окончательно определился в направлении движения общества в сторону демократизации, и в этом движении С. Круглову, как министру внутренних дел, места не оставалось. За несколько дней до начала съезда, а точнее - 6, 8, 10 и 11 февраля, в МВД СССР работала правительственная комиссия, собранная по случаю ухода с министерского поста С. Круглова. Имя нового министра было уже известно - им оказался 49-летний Николай Дудоров, до этого никакого отношения к правоохранительной системе не имевший. С конца 30-х годов, начав работать на строительных должностях, Н. Дудоров к 1954 году вырос до заведующего Отделом строительства ЦК КПСС. Таким образом, он оказался первым строителем в советской истории, ставшим волею судьбы министром внутренних дел СССР. Ровно через 32 года его путь на этом поприще повторит и Вадим Бакатин.
Тот факт, что для передачи дел в министерстве от одного министра другому создали правительственную комиссию во главе с секретарем ЦК Аверкием Аристовым, было явлением беспрецедентным и указывало на решение Хрущева разделаться с Кругловым одним ударом. Вместе с правительственной комиссией в составе 5 человек образовали еще 6 подкомиссий из работников отдела административных органов ЦК КПСС, Министерства госконтроля СССР, Минюста СССР, Минобороны СССР, Прокуратуры СССР и союзного Минфина.
Вывод авторитетной комиссии был весьма однозначен: "Министерство внутренних дел СССР неудовлетворительно выполняет поставленные перед ним партией и правительством задачи... Бывший министр т. Круглов, члены коллегии и др. руководящие работники МВД СССР не сделали должных выводов из постановлений ЦК КПСС 1953 года... В работе МВД СССР преобладает канцелярско-бюрократический стиль руководства местными органами МВД. Критика и самокритика в МВД не была развита".
Вспомнили С. Круглову и недавние бунты в лагерях ГУЛАГа. "ЦК КПСС своими постановлениями от 12 марта и 10 июля 1954 года обязал руководство МВД СССР принять меры к коренному улучшению дела перевоспитания заключенных путем укрепления режима их содержания и приобщения к общественно-полезному труду. Руководство МВД СССР безответственно отнеслось к выполнению этих постановлений, не навело порядка в режиме содержания осужденных в местах заключения, не справилось с задачей правильной организации их трудового воспитания".