В кадровой политике КГБ Иван Серов опирался как на старых чекистов, так и на новых партийных выдвиженцев. При нем были заменены практически все руководители подразделений центрального аппарата. Первыми зампредами КГБ при нем стали партработник Константин Лунев (после отставки шефа исполнял обязанности председателя КГБ, затем отправлен в почетную ссылку в Казахстан — Председателем КГБ при СМ Казахской СССР) и военный контрразведчик Петр Ивашутин (с 5 по 13 ноября 1961 года исполнял обязанности председателя КГБ, с марта 1963 по 1988 год — руководитель Главного разведывательного управления ГШ МО СССР (ГРУ)); зампредами — бывший руководитель управления кадров и шифровальных органов Иван Савченко, партаппаратчики Петр Григорьев (руководил Управлением кадров) и Василий Лукшин; разведку возглавляли разведчик и дипломат Александр Панюшкин и контрразведчик Александр Сахаровский; контрразведку — старый чекист Петр Федотов и более молодой (в 1956 году, когда он был назначен, ему исполнился 41 год) Олег Грибанов; борьбой с «антисоветскими элементами» руководил бывший зам Виктора Абакумова Евгений Питовранов.

Никто из них не был человеком Ивана Серова. Его бывшие сослуживцы по МВД на руководящие посты в КГБ не перешли. В отличие от многих своих предшественников и преемников, он не тащил за собой свою команду. Но это может также свидетельствовать и о том, что ее у него не было.

Структура центрального аппарата КГБ, сформировавшиеся при Иване Серове, поражала своей скромностью (по сравнению с НКВД марта 1942 года, когда функционировало более 65 управлений и приравненных к ним отделов).

В 1956 году центральный аппарат КГБ имел такую структуру:

Первое Главное управление (разведка), Второе Главное управление (контрразведка), Третье Главное управление (военная контрразведка), Четвертое управление (антисоветское подполье, националистические формирования и враждебные элементы),