Молотов, Булганин и другие по очереди выступили с осуждением Берии. Перед тем как перейти к официальному голосованию по предложению Хрущева, Маленков нажал потайную кнопку под столом. Вошел Жуков во главе группы вооруженных армейских офицеров, арестовал Берию и увел его под конвоем. В портфеле Берии был найден листок бумаги, на котором он написал красным «Тревога» в надежде, что ему удастся вызвать подмогу. Опасаясь, что войска МВД попытаются освободить своего шефа, Жуков ввел в Москву две дивизии — танковую и мотострелковую, которые при необходимости могли подавить выступление частей МВД, вооруженных лишь стрелковым оружием. Лишь несколько дней спустя офицерам МВД официально сообщили, что Берия арестован. Для многих первым признаком падения Берии стало исчезновение его портретов. В начале июля четырнадцатилетний Гордиевский, который в то время был на каникулах на Украине, получил письмо от своего отца — полковника Управления учебных заведений МВД, в котором тот писал: «Вчера произошло событие невероятное. Со стен сняли портреты шефа.» Через несколько дней пришло второе письмо с такой новостью: «Шефа арестовали и держат в тюремной камере.»

Официально об аресте Берии было объявлено 10 июля. Хрущев, возглавивший переворот, стал теперь главным в руководстве, которое все еще официально именовалось коллегиальным. В сентябре он занял пост Первого секретаря ЦК партии. 24 декабря было объявлено, что Берию и шесть его подручных (среди них Меркулов, бывший начальник НКГБ, и Деканозов, бывший начальник ИНУ) Верховный суд признал виновными в заговоре с целью «возрождения капитализма и реставрации власти буржуазии». Самое страшное преступление Берии — ответственность за массовые убийства — не могло быть упомянуто из опасения, что это дискредитирует режим. В сообщении о казни вскользь упоминались преступления, «свидетельствующие о его моральном падении». На закрытом процессе над Берией Верховному суду сообщили, что у одного из охранников Берии был обнаружен клочок бумаги с именами и телефонами четырех из сотен женщин, которых затаскивали к нему домой во Вспольном переулке, где он их насиловал. Среди этих жертв была шестнадцатилетняя девочка.

Самым выдающимся из всех предъявленных Берии обвинений было сотрудничество с британской разведкой. Единственным свидетельством его связи с английской разведкой, представленным на суде, было досье из его личного архива, из которого якобы явствовало, что во время Гражданской войны, в 1919 году, он работал на контрразведку националистического мусаватисткого режима в Баку, то есть в то время, когда этот регион контролировали англичане. Один из следователей по делу Берии признал впоследствии, что в том досье ничего не говорилось «ни о заданиях, которые давали Берии, ни о том, как он их выполнял». Однако в официальном сообщении о суде над Берией отмечалось, что с 1919 года «и до самого ареста Берия не прерывал и расширял свои тайные связи с иностранной разведкой». Таким образом, вслед за Ягодой и Ежовым, которых казнили в тридцатых годах, Берия стал третьим руководителем КГБ, казненным за преступления, среди которых было и обвинение в работе на английскую разведку.

После ареста Берии 26 июня его место на посту главы МВД занял один из его бывших заместителей, Сергей Круглов, который присоединился к заговорщикам. В то время бывшее МГБ пока продолжало оставаться в составе МВД. Рясной, которого Берия поставил во главе Иностранного управления, был уволен, и след его затерялся (хотя вряд ли где-нибудь в ГУЛАГе). На смену ему пришел дипломат Александр Семенович Панюткин, возможно, по предложению Молотова, который после смерти Сталина снова стал министром иностранных дел. Молотов хотел восстановить свое былое влияние на внешнюю разведку, которым он пользовался, когда создавался КИ. С 1947 по 1952 год Панюшкин был послом в Вашингтоне и в течение какого-то времени до и после этого периода — послом в Пекине. Кроме того, что он был главным легальным резидентом в Вашингтоне в период деятельности КИ, он также осуществлял непосредственное руководство операциями в течение года после отзыва легального резидента Георгия Соколова в 1949 году. Один из перебежчиков более позднего периода вспоминал, что в 1953 году Панюшкин был высокий, худощавый, несколько сутулый, в сером костюме и с землистым цветом лица («какой бывает у шахтеров или рабочих свинцовых заводов»), в то же время человек он был простой, без претензий. Его представление сотрудникам Иностранного управления состоялось в актовом зале Дома офицеров. Петр Дерябин, в то время секретарь одной из парторганизаций, встретил его у входа в Дом офицеров и проводил на сцену, где уже сидели Круглов, его заместитель Иван Серов и другие секретари парторганизаций. Круглов сообщил о назначении Панюшкина, затем Панюшкин вкратце рассказал, чем занимался до этого, и предложил задавать вопросы. Пораженные такой сравнительно неофициальной атмосферой, присутствовавшие молчали, и встреча на этом закончилась. То, что Панюшкин в прошлом был дипломатом, ни в коей мере не означало, что методы зарубежной деятельности МВД будут как-то смягчены. И действительно, одной из первых операций, которую Панюшкин лично контролировал из Центра, стала операция «Рейн» — попытка покушения на лидера украинской эмиграции в Западной Германии. За поколение до этого, в ходе операции «Трест» удалось выкрасть двух основных лидеров белой эмиграции — генералов Кутепова и Миллера, которых не удавалось заманить обратно в Советский Союз. После серии подобных операций, удачно проведенных в начале холодной войны вдоль советской границы, к ликвидации были намечены наиболее влиятельные лидеры эмиграции — руководители Народно-трудового союза (НТО в Западной Германии. Убийство первой предполагаемой жертвы, Георгия Сергеевича Околовича, санкционировалось, как и все операции по ликвидации за рубежом, непосредственно Президиумом. За подготовкой Николая Хохлова, назначенного старшим группы МВД по ликвидации, наблюдал сам Панюшкин. Среди инструкторов Хохлова был Михайл Рубак, чемпион СССР по самбо, и подполковник Годлевский, пятикратный чемпион Союза по стрельбе из пистолета. Орудие убийства — пистолет с электрическим спуском и с глушителем — было спрятано в пачке сигарет. Пистолет, стрелявший пулями, отравленными цианистым калием, был разработан в секретной оружейной лаборатории МВД/МГБ. Однако Хохлов оказался более разборчивым, чем убийцы сталинской эпохи. Его по крайней мере наполовину убедили некоторые публикации НТС, с которыми он познакомился, готовясь к покушению на Околовича. 18 февраля 1954 года Хохлов зашел на квартиру Околовича во Франкфурте и представился, повергнув хозяина квартиры в полное замешательство. «Георгий Сергеевич, — обратился он к Околовичу, — я прибыл из Москвы. Центральный Комитет Коммунистической партии Советского Союза приказал вас ликвидировать. Убийство поручено моей группе.» Затем он сообщил перепуганному Околовичу, что решил не убивать его. Вместо этого Хохлов переметнулся в ЦРУ, где поначалу к нему отнеслись довольно скептически. 20 апреля состоялась сенсационная пресс-конференция, на которой он поведал о плане покушения и продемонстрировал орудие убийства. С начала холодной войны в советской разведке не было серьезных случаев измены. Но бегство Хохлова стало первым из пяти крупнейших скандалов, которые Московскому центру предстояло пережить в первые месяцы 1954 года. В январе Юрий Растворов, сотрудник резидентуры в Токио, перебежал в ЦРУ; в феврале в Вене, и тоже в ЦРУ, бежал Петр Дерябин; а в апреле в Канберре остались Владимир и Евдокия Петровы.

В марте 1954 года советская система госбезопасности претерпела последнюю крупную реорганизацию со времени войны. МГБ было вновь выведено из состава МВД, но статус этого учреждения стал на порядок ниже: из министерства оно превратилось в Комитет государственной безопасности (или КГБ), официально прикрепленный к Совету Министров, чтобы можно было держать это ведомство под политическим контролем. Первым председателем КГБ стал бывший заместитель Круглова, сорокадевятилетний генерал Иван Александрович Серов, известный, главным образом, своей жесткой хваткой, с которой во время войны осуществлял депортации на Кавказе и подавлял сопротивление коммунистическому режиму в Прибалтике и Восточной Европе. Хрущев, который собственно и назначил Серова, позже вспоминал о нем так: «С Кругловым я был мало знаком, но я хорошо знал Серова и верил ему… Если и есть в нем что-то сомнительное, как и во всех чекистах, то скажем просто, что он был жертвой общей сталинской политики.»

Богатый опит Серова по подавлению инакомыслия сослужил ему хорошую службу во время самого серьезного кризиса, произошедшего за пять лет его пребывания на посту руководителя КГБ, — революции в Венгрии 1956 года. Подавление революции также наложило отпечаток на репутацию нового поколения руководителей КГБ. В 1954 году советским послом в Будапеште в возрасте сорока лет стал будущий председатель КГБ Юрий Владимирович Андропов, стройный, изысканный, элегантно одевавшийся в дорогие, хорошо сшитые костюмы. В 1955 году еще один будущий председатель КГБ, Владимир Александрович Крючков, в возрасте тридцати одного года, прибыл в Будапешт для работы в качестве одного из третьих секретарей Андропова. Роль Крючкова в подавлении революции 1956 года позже стала невыгодным фактом его биографии. До 1984 года в его официальной биографии депутата Верховного Совета не содержалось никакого упоминания о том времени, когда он был в Будапеште. Однако, став в 1988 году председателем КГБ, Крючков признал, что он лицом к лицу столкнулся с «событиями» (как он их эвфемистично назвал) в Венгрии в 1956 году. «Но оглядываясь сегодня назад, я многое вижу в ином свете, и это вполне естественно.» Сегодня Крючков также утверждает, что он искренний поклонник венгерской литературы, но, к сожалению, не всегда находит время на чтение.

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

На состоявшемся в тот вечер чрезвычайном заседании Министерства внутренних дел Серов был представлен как новый советский советник, причем имя его названо не было. Делая ударение на каждом слове, Серов сообщил собравшимся: «Фашисты и империалисты выводят свои ударные силы на улицы Будапешта. И все же находятся товарищи в вооруженных силах вашей страны, которые сомневаются, применять ли им оружие.» Шандор Копачи, начальник будапештской полиции, который вскоре перешел на сторону борцов за свободу, ответил с нескрываемым презрением: «Видимо, товарищ советник из Москвы не успел изучить обстановку в нашей стране. Надо сказать ему, что на демонстрацию вышли не фашисты и прочие империалисты, а студенты университетов, лучшие сыны и дочери рабочих и крестьян, цвет нашей интеллигенции, и они требуют осуществления своих прав, хотят выразить сочувствие полякам и проявить с ними солидарность.» Четверть века спустя Копачи все еще не мог забыть долгий испепеляющий взгляд стальных глаз Серова.