Уход с политической сцены Сталина не повлек за собой ослабления партийного контроля за деятельностью органов государственной безопасности. Как и при Сталине, органы безопасности в состав Совета министров Союза ССР входили лишь номинально, а фактически были непосредственно подчинены первому липу в партии. Подобный порядок подчиненности органов носил повсеместный характер. Он действовал на всех уровнях: в республиках, краях, областях и районах.
Извлекая уроки из дела Берии, руководство партии посчитало, что МВД приобрело в стране непомерно большое влияние. Оценивая подобную ситуацию как опасную, ЦК КПСС принял решение о выводе оперативных подразделений, обеспечивающих безопасность страны, из состава МВД и создании на их базе самостоятельного государственного органа, но не в статусе министерства, подобно бывшему МГБ, а с понижением до уровня комитета при Совете министров СССР со всеми вытекающими из этого правовыми и финансовыми последствиями. Так родилось 13 марта 1954 года новое ведомство — Комитет государственной безопасности при СМ СССР (КГБ).
Избранная система построения и подчиненности органов КГБ вписывала их в конституционное поле государства, усиливала контроль и обеспечивала коллегиальность управления ими. Образованная в КГБ коллегия наделялась не совещательным, а решающим правом. Коллегиальность руководства действовала и во всех звеньях структуры КГБ через созданные коллегии в республиках и советы в краевых и областных управлениях. В состав коллегии (не всегда) и советов на местах входили представители военной контрразведки.
В результате реорганизации органов военную контрразведку в центре стало представлять 3-е управление КГБ при СМ СССР. Ее периферийным органам снова возвратили наименование особых отделов. В это понятие включались все подразделения армейской контрразведки сверху донизу, от особого отдела военного округа до особого отдела бригады и гарнизона. В действующей системе военной контрразведки того времени имелось только два управления особых отделов КГБ — в Группе советских войск в Германии и Дальневосточном округе.
Первым председателем Комитета госбезопасности по рекомендации Хрущева правительство назначило И.А. Серова, и это неслучайно: Хрущев близко знал Серова по совместной работе до войны на Украине, где тот руководил Наркоматом внутренних дел. Хрущев считал Серова послушным ему человеком, на которого можно опереться. После образования КГБ, весной 1954 года, Хрущев лично принял участие в собрании руководящего состава Комитета. Я хорошо помню представление им собранию Серова и выступление Хрущева с большой, как обычно, импровизированной и грубо скроенной речью, в которой он, подбадривая личный состав КГБ, заявил, что Центральный комитет партии, несмотря на события, вызванные арестом Берии и его приспешников, по-прежнему доверяет сотрудникам госбезопасности и они могут продолжать уверенно трудиться.
Заверения Хрущева опровергли последующие события. С марта 1954 по февраль 1956 года из органов КГБ было уволено 16 тысяч сотрудников «как не внушающих политического доверия, злостных нарушителей социалистической законности, карьеристов, морально неустойчивых, а также малограмотных и отсталых работников». Так докладывал Серов в ЦК КПСС. Сам Серов не оставлял впечатления солидного руководителя с широким политическим кругозором.
В декабре 1958 года Серов был освобожден от обязанностей председателя КГБ и назначен начальником Главного разведывательного управления Генерального штаба Вооруженных сил СССР (ГРУ). Работая в военной разведке, он в начале 1963 года пережил серьезные неприятности, потерпев фиаско в связи с делом разоблаченного органами безопасности англо-американского шпиона Пеньковского. Серов после увольнения Пеньковского из ГРУ не только вторично взял его на работу, но и приблизил к себе, давая ему отдельные личные поручения, в том числе и за границей. «За потерю политической бдительности и недостойные поступки» Серова сняли с должности руководителя ГРУ, разжаловали в генерал-майора и лишили звания Героя Советского Союза.
После ухода в 1958 году Серова управление Комитетом госбезопасности около десяти лет оставалось в руках бывших лидеров комсомола А.Н. Шелепина и В.Е. Семичастного. Они привели с собой руководящих комсомольских работников, поставив их во главе крупных периферийных органов, в частности Ленинградского, Ростовского и других управлений КГБ.
Следуя путем хрущевских реформ, Шелепин провел крупные мероприятия, направленные на упрощение структуры центрального аппарата, сокращение численности органов и войск КГБ, освобождение органов безопасности от несвойственных им функций. Мероприятия, в частности, включали в себя ликвидацию тюремного отдела и сокращение тюрем КГБ. В 1960 году отдельные подразделения КГБ, в их числе и 3-й главк (военная контрразведка), были понижены в статусе и стали именоваться просто управлениями. Шелепин ввел в практику включение в состав коллегии Комитета руководителей крупных периферийных органов — Украины и Ленинграда.