В марте 1954 года советская система госбезопасности претерпела последнюю крупную реорганизацию со времени войны. МГБ было вновь выведено из состава МВД, но статус этого учреждения стал на порядок ниже: из министерства оно превратилось в Комитет государственной безопасности (или КГБ), официально прикрепленный к Совету Министров, чтобы можно было держать это ведомство под политическим контролем. Первым председателем КГБ стал бывший заместитель Круглова, сорокадевятилетний генерал Иван Александрович Серов, известный, главным образом, своей жесткой хваткой, с которой во время войны осуществлял депортации на Кавказе и подавлял сопротивление коммунистическому режиму в Прибалтике и Восточной Европе. Хрущев, который собственно и назначил Серова, позже вспоминал о нем так: «С Кругловым я был мало знаком, но я хорошо знал Серова и верил ему… Если и есть в нем что-то сомнительное, как и во всех чекистах, то скажем просто, что он был жертвой общей сталинской политики.»
Богатый опит Серова по подавлению инакомыслия сослужил ему хорошую службу во время самого серьезного кризиса, произошедшего за пять лет его пребывания на посту руководителя КГБ, — революции в Венгрии 1956 года. Подавление революции также наложило отпечаток на репутацию нового поколения руководителей КГБ. В 1954 году советским послом в Будапеште в возрасте сорока лет стал будущий председатель КГБ Юрий Владимирович Андропов, стройный, изысканный, элегантно одевавшийся в дорогие, хорошо сшитые костюмы. В 1955 году еще один будущий председатель КГБ, Владимир Александрович Крючков, в возрасте тридцати одного года, прибыл в Будапешт для работы в качестве одного из третьих секретарей Андропова. Роль Крючкова в подавлении революции 1956 года позже стала невыгодным фактом его биографии. До 1984 года в его официальной биографии депутата Верховного Совета не содержалось никакого упоминания о том времени, когда он был в Будапеште. Однако, став в 1988 году председателем КГБ, Крючков признал, что он лицом к лицу столкнулся с «событиями» (как он их эвфемистично назвал) в Венгрии в 1956 году. «Но оглядываясь сегодня назад, я многое вижу в ином свете, и это вполне естественно.» Сегодня Крючков также утверждает, что он искренний поклонник венгерской литературы, но, к сожалению, не всегда находит время на чтение.
В середине пятидесятых годов Андропов, да пожалуй и Крючков, очень скоро увидели в неосталинизме Ракоши серьезную помеху власти коммунистов в Венгрии. Этот курс был еще более серьезно скомпрометирован после закрытого выступления Хрущева на XX съезде Коммунистической партии в феврале 1956 года, текст которого четыре месяца спустя был опубликован на Западе. В этом докладе осуждался «культ личности» Сталина и вытекающие из него «серьезнейшие и глубочайшие извращения принципов партийности, партийной демократии и революционной законности». 17 июля 1956 года Микоян вылетел в Будапешт и убедил Ракоши уйти с поста Первого секретаря якобы по состоянию здоровья и переехать в Советский Союз. Однако вместо популярного прогрессиста Имре Надя его преемником стал представитель «старой гвардии» Эрне Герэ. Падение Ракоши и сообщения о реформах в Польше усилили стремление общественности к реальным политическим переменам. Немало этому способствовало и состоявшееся 6 октября торжественное перезахоронение останков Ласло Райка, который был посмертно реабилитирован. В октябре, на фоне обостряющегося венгерского кризиса, был отозван в Москву главный советник КГБ генерал Емельянов. В Будапешт вылетел сам генерал Серов, чтобы взять руководство на себя. Впервые председатель КГБ лично руководил крупной операцией за пределами России. 23 октября студенческая демонстрация собрала примерно двести пятьдесят тысяч человек, которые вышли на улицы Будапешта, чтобы потребовать проведения свободных выборов, возвращения Имре Надя и вывода советских войск. Чуть позже девяти часов вечера сотрудники АВХ застрелили нескольких участников мирной демонстрации у Дома радио. Когда, прячась в машине скорой помощи, приехало подкрепление АВХ, толпа отобрала у них оружие. Несколько часов спустя борцы за свободу получили оружие от сочувствующих полицейских и солдат, а также с оружейных складов. Сталелитейщики сбросили с пьедестала огромный памятник Сталину, который со страшным грохотом рухнул на землю. Так началась революция.