Вопреки бытующему мнению о том, что именно в период массовых репрессий Сталин истребил всех старых чекистов, статистические данные говорят о том, что в 1937–1938 годах в руководящем звене НКВД основной костяк (более 70 процентов) составляли «истинные чекисты» (дзержинцы), поступившие на службу с начала создания органов госбезопасности и до середины двадцатых годов. Их руками как раз и проводились репрессии. Вместе с тем Сталина беспокоила высокая «засоренность» старых чекистских кадров выходцами из «чуждых» классов (помещиков, торговцев, предпринимателей, служителей культа), участниками небольшевистских партий и движений (эсерами, меньшевиками, анархистами, бундовцами) и представителями «нетитульных» национальностей. В связи с этим, под маркой борьбы с заговором право-троцкистского блока, в период ежовского правления была проведена «чистка» главным образом сторонников Ягоды. Оставшиеся «неблагонадежные» руководители были уволены либо арестованы с началом бериевского правления, в конце 1938 и начале 1939 годов [9].
После практического завершения работы по привлечению к уголовной ответственности, наказанию в партийно-административном порядке и увольнению ряда печально прославившихся руководителей правоохранительных органов решением Политбюро ЦК ВКП(б) от 27 февраля 1939 года Круглову С.Н. было поручено возглавить работу с кадрами в Наркомате внутренних дел. В соответствии с принятым на следующий день постановлением СНК СССР и объявлявшим это решение приказом № 373 от 28 февраля 1939 года майор госбезопасности Круглов С.Н. получил назначение на должность заместителя наркома внутренних дел СССР по кадрам и начальника Отдела кадров НКВД СССР. Ведавшего до этого кадрами полковника Давыдова Н.К. направили начальником Центральной школы НКВД СССР.
Теперь расстановка руководства НКВД СССР выглядела следующим образом. Наркомом внутренних дел являлся комиссар госбезопасности I ранга Берия Л.П. Обязанности его первого заместителя и начальника Главного управления государственной безопасности (ГУГБ) исполнял комиссар госбезопасности III ранга Меркулов В.Н. Заместителем наркома по войскам был комбриг Масленников И.И. Должности заместителя наркома и начальника Главного управления лагерей (ГУЛАГ) совмещал комдив Чернышов В.В. Заместителем наркома по кадрам, как уже отмечалось, стал майор госбезопасности Круглов С.Н. [4].
По своему составу Наркомат внутренних дел того времени имел следующую структуру. В него входили одиннадцать главных управлений: Главное управление государственной безопасности (ГУГБ), Главное экономическое управление (ГЭУ), Главное транспортное управление (ГТУ), Главное управление пограничных и внутренних войск (ГУПВВ), Главное управление рабоче-крестьянской милиции (ГУРКМ), Главное управление лагерей (ГУЛАГ), Главное управление шоссейных дорог (ГУШОСДОР), Главное управление пожарной охраны (ГУПО), Главное тюремное управление (ГТУ), Главное архивное управление (ГАУ) и Главное управление строительства на Дальнем Севере (ГУСДС) или Дальстрой. Далее структура наркомата включала Административно-хозяйственное управление (АХУ) и отделы: 1 спецотдел (учётно-регистрационный), 2 спецотдел (опертехники), 3 спецотдел (обыски, аресты, наружное наблюдение), Центральный отдел актов гражданского состояния (ЦОАГС), Центральный финансово-плановый отдел (ЦФПО), Отдел кадров (ОК), Переселенческий отдел, а также Особоуполномоченный НКВД СССР со своим аппаратом, Особое конструкторское бюро (ОКБ), Бюро по приёму и рассмотрению жалоб, Инспекция по котлонадзору, Секретариат НКВД СССР. К системе НКВД относились также Центральный совет спортивного общества «Динамо» и Центральный клуб сотрудников НКВД СССР [4].
Эта структура, которая должна была постоянно укомплектовываться квалифицированными и преданными делу партии кадрами, не оставалась неизменной, а периодически видоизменялась в соответствии с указаниями Сталина И.В. Так, только в 1939 году в её составе произошёл ряд существенных преобразований. В преддверии приближавшейся войны наиболее значительные изменения коснулись Главного управления пограничных и внутренних войск, которое было разделено на шесть главных управлений: Главное управление погранвойск (ГУПВ), Главное управление войск НКВД СССР по охране железнодорожных сооружений, Главное управление войск НКВД СССР по охране особо важных предприятий промышленности, Главное управление конвойных войск НКВД СССР, Главное управление военного снабжения (ГУВС) и Главное военно-строительное управление войск (ГВСУ) НКВД СССР. Затем были сформированы Мобилизационный отдел, Отдел железнодорожных и водных перевозок, Управление НКВД СССР по делам военнопленных и интернированных, а также произведён ещё ряд более мелких преобразований. В результате по состоянию на 1 января 1940 года в центральном аппарате НКВД СССР по штату числилось 32642 человека [4].