На XX партийном съезде в феврале 1956 года Серов был избран в члены ЦК КПСС, он также избирался депутатом Верховного Совета РСФСР 4-го (1955–1959) и 5-го (1958–1962) созывов.
В ноябре 1956 года И.А. Серов участвовал в подавлении народного восстания в Венгрии. События в Венгрии и Польше напугали руководство КПСС, и весной 1957 года Хрущев на встрече с писателями заявил: «Если кто думает сделать так, как в Венгрии, — в порошок сотрем». Серов четко уловил новую установку, и в 1957 году КГБ произвел рекордное количество арестов за «контрреволюционные преступления».
Доверие Хрущева Серов оправдывал везде, даже в зарубежных поездках. В конце 1955 года Н. Булганин и Хрущев, отправляясь в месячную командировку в Индию, Бирму и Афганистан, для обеспечения «личной безопасности» взяли с собой И.А. Серова. Он также сопровождал их в мае 1956 года во время поездки в Великобританию, и в июне 1957 года — в Финляндию.
Последний свой служебный визит за границу в качестве Председателя КГБ И.А. Серов нанес осенью 1958 года в ГДР.
Один из руководителей СВР, В. Кирпиченко, так вспоминал о нем: «Небольшого роста, быстрый в движениях, Серов не мог подолгу сидеть на одном месте и доставлял много хлопот охране… От него исходили флюиды нервозности и непостоянства. Иногда оперработники с оттенком иронии говорили, что он и внешне, и по характеру похож на генералиссимуса Суворова, что, конечно, доходило до ушей Серова и, надо полагать, доставляло ему большую радость… Когда кампания по разоблачению Берии и чистке чекистских рядов несколько утихла, Серов начал заниматься и делами разведки, которые находились в запущенном состоянии вследствие волюнтаристских действий Берии…» Встречался с ним и Кирпиченко. «Разговор носил формальный характер. Серов высказал ряд общих, уже набивших оскомину рекомендаций, вроде того, что нужно много работать, проявлять инициативу, вербовать агентуру, направлять информацию и так далее… Обмениваясь после встречи мнениями о председателе КГБ, мы дружно отметили его неосведомленность в вопросах внешней политики, небогатый словарный запас, а то, что он представлял себе египтян чернокожими африканцами, нас просто шокировало… В связи с уходом Серова с поста председателя никто в КГБ особых сожалений не высказывал, а начальник разведки А.М. Сахаровский даже вздохнул облегченно, выразив надежду, что с новым руководителем легче будет договариваться по всему кругу вопросов деятельности разведки».
Неожиданно 8 декабря 1958 года указом Президиума Верховного Совета СССР И.А. Серов был освобожден от обязанностей председателя КГБ при СМ СССР и через два дня назначен начальником Главного разведывательного управления — заместителем начальника Генерального штаба ВС СССР. Для Серова это стало явным понижением, однако в решении Президиума ЦК КПСС от 10 декабря 1958 года новое назначение объяснялось необходимостью укрепления руководства ГРУ и говорилось о сохранении за ним прежнего денежного содержания.
Что же послужило причиной освобождения И.А. Серова с должности председателя КГБ? Причастность к наиболее ужасным сталинским преступлениям не была ни для кого секретом, строго наказывать Серова за это Хрущев не собирался, но и оставлять на должности председателя КГБ тоже не хотел. Хрущев стремился отмежеваться от карательной службы и ее мрачного прошлого. По его мнению, настало время реформировать КГБ, уменьшить численность, изменить структуру, смягчить карательную политику комитета. Вероятно, Хрущеву не нравился ведомственный патриотизм Серова и его нежелание сокращать аппарат КГБ. Хрущев полагал, что КГБ должен руководить функционер, безропотно выполняющий любые партийные решения. На должность председателя КГБ был назначен 25 декабря 1958 года А. Шелепин, возглавлявший до этого отдел партийных органов ЦК КПСС по союзным республикам.