Много лет близко знавший (и лечивший) Брежнева академик Е. И. Чазов подчеркивает в своих мемуарах, что «как политик, как знаток политической борьбы он был выше всех. Он был достойным учеником своего учителя Н. С. Хрущёва. Он прекрасно знал человеческую натуру и человеческие слабости. Что значило для секретаря обкома или секретаря крупного горкома, которые в то время определяли жизнь партии на местах, когда первый секретарь ЦК КПСС звонит, иногда поздно вечером, иногда и во время своего отпуска, и интересуется делами партийной организации, спрашивает: как виды на урожай, что с промышленностью, что нового в области, ну и, конечно, как ты себя чувствуешь и чем тебе, дорогой, помочь? Этим ли путем или просто постепенной, незаметной на первый взгляд заменой старых секретарей на более молодых и лояльных, но он обеспечил себе к XXIII съезду партии поддержку подавляющего большинства партийной элиты».
В марте 1966 г. состоялся XXIII съезд КПСС, первый съезд при новом руководстве. Все прошло как по нотам. Брежнев сделал пятичасовой доклад. Многие ждали, что он попытается реабилитировать Сталина. Однако в речи Брежнева имя Сталина было упомянуто лишь однажды (в связи с победой в войне). Таким образом, до сих пор бытующая версия, что смещение Хрущёва было организовано для того, чтобы реабилитировать Сталина и окончательно задавить робкие ростки демократии, никак не подтверждается.
На съезде выступил первый секретарь Московского горкома партии Н. Г. Егорычев, который, ссылаясь на Ленина, предложил восстановить должность генерального секретаря и Политбюро. Оба решения съезд единодушно поддержал – и Брежнев стал Генеральным (именно так, с большой буквы, и будет в дальнейшем писаться его должность, как и должность всех его преемников).
В июле 1966 г. состоялось еще одно ключевое назначение. Было воссоздано общесоюзное Министерство охраны общественного порядка, упраздненное Хрущёвым (с 1968 г. Министерство внутренних дел). И министром, преодолев некоторое сопротивление в Президиуме ЦК КПСС, Брежнев назначил своего давнего и верного соратника Н. А. Щёлокова, вызвав его из Молдавии, где тот был вторым секретарем республиканской Компартии. Сейчас Щёлоков прежде всего ассоциируется с «брежневской коррупцией» (и действительно, безгрешен он не был, хотя по современным меркам вся эта «коррупция» выглядела убого). Однако как министр он сделал много полезного. Например, при нем в системе МВД появились научные институты, изучавшие различные проблемы криминалистики, предлагавшие новые методы раскрытия преступлений, и т. д. Как и его вечный антагонист Андропов, Щёлоков предпринимал серьезные усилия для улучшения имиджа своего ведомства. Авторы милицейских детективов получали престижные премии, снимались сериалы (из наиболее популярных можно вспомнить «Следствие ведут знатоки», «Место встречи изменить нельзя» и «Рожденная революцией»), День милиции 10 ноября стал заметным праздником (по крайней мере концерты в этот день были чуть ли не лучшими в году).
Политические игры в верхах в основном закончились в 1967 году, когда Брежнев окончательно избавился от трех сильных и самостоятельных фигур. В мае он снял Семичастного с должности председателя КГБ, в июне убрал Егорычева с поста первого секретаря Московского горкома КПСС, а в сентябре Шелепин лишился поста секретаря ЦК.
7 марта 1967 г. дочь Сталина Светлана Аллилуева, находившаяся в Индии, попросила политического убежища в американском посольстве в Дели. Эта ситуация вызвала сильное раздражение политического руководства. Но сам Брежнев решил воспользоваться этим в своих интересах. Немного выждав, в мае 1967 г., он предложил снять Семичастного с должности председателя КГБ, причем в вину ему, помимо прочего, поставили побег Аллилуевой. Момент был выбран точно – покровитель и союзник Семичастного Шелепин как раз лежал в кремлевской больнице, ожидая срочной операции. Семичастный отправился на Украину первым заместителем председателя Совета министров (эту должность добавили специально для него), а председателем КГБ неожиданно для многих стал секретарь ЦК Ю. В. Андропов. Андропов не принадлежал к брежневской команде, не был особенно близок с Генеральным секретарем, и тем не менее Брежнев выбрал именно его. Тут стоит упомянуть, что Андропов был советским послом в Будапеште в 1956 году и навсегда запомнил повешенных на фонарях венгерских коммунистов и офицеров органов безопасности. Отсюда его жесткая политика в отношении любой оппозиции как внутри СССР, так и в социалистическом лагере в целом. Впрочем, без присмотра осторожный Брежнев его не оставлял – первым заместителем Андропова был назначен давний соратник Брежнева по Молдавии С. К. Цвигун, а в октябре 1970 г. еще одним его заместителем стал другой доверенный человек Леонида Ильича, муж его двоюродной сестры Г. К. Цинев.