После XXIII съезда КПСС влияние Брежнева в руководстве ЦК заметно укрепилось, но для многих западных наблюдателей все еще было неясно, кто именно принимает решения или – хотя бы – кто является «главным» в Кремле. Когда в июне 1966 года в Москву прибыл для переговоров президент Франции Шарль де Голль, то в центре внимания публики оказался не только гость, но и принимавшие его по протоколу Подгорный и Косыгин. Однако во время переговоров в Кремле фактическим главой советской делегации был Брежнев. Французам он показался очень твердым руководителем.

19 декабря 1966 года Брежневу исполнилось 60 лет. В этот день в Москве проходило заседание Верховного Совета СССР по случаю утверждения бюджета и плана на 1967 год. В печати появилось специальное послание Брежневу от ЦК КПСС, Совета Министров СССР и Президиума Верховного Совета СССР, где его именовали уже «выдающимся» руководителем. Брежневу было присвоено звание Героя Советского Союза, и Подгорный приколол на безупречный, как всегда, костюм юбиляра Золотую Звезду Героя. Когда Брежнев занимал свое место в президиуме Большого Кремлевского дворца, депутаты Верховного Совета поднялись со своих мест и устроили ему бурную овацию. Заседание было прервано. Председатель Совета Союза И. В. Спиридонов произнес специальную речь в честь Брежнева. В ответной речи Брежнев обещал оправдать доверие и посвятить остаток своей жизни неустанной работе на благо народа и партии.

Но Брежнев не мог считать свою власть прочной, пока контроль за работой КГБ находился в руках Шелепина и пока связи его самого с верхами армии не были еще достаточно прочными. Нужный повод для изменения руководства КГБ скоро нашелся. В марте 1967 года произошло необычное событие – сбежала на Запад и вскоре оказалась в США дочь Сталина Светлана Аллилуева. Это событие достаточно хорошо освещено в самых различных статьях и книгах, в том числе и в книге самой С. Аллилуевой «Только один год». Бегство Аллилуевой вызвало поначалу большое беспокойство в Политбюро, и не только потому, что речь шла о дочери Сталина, что, разумеется, не могло радовать всех тех, кто стремился к реабилитации Сталина. Аллилуева много знала о нравах и обычаях высших слоев советского общества, она была при этом достаточно образованным, как казалось некоторым ее друзьям, филологом и имела даже научную степень кандидата филологических наук. Еще до того как Аллилуева объявилась в США, она провела две-три недели в Италии и «где-то» в Швейцарии. Комитет государственной безопасности СССР получил задание вернуть Аллилуеву в Москву, и кто-то из ответственных сотрудников КГБ срочно начал действовать. Поводом для смещения Семичастного послужили отдельные недостатки советских спецслужб, связанные с побегом Аллилуевой за границу, хотя это было не единственное обвинение, которое предъявлялось КГБ и его руководству. Семичастный имел, однако, сильного покровителя в лице Шелепина, которого Брежнев все еще опасался. В Москве обратили внимание, что, выезжая 1967 года в Берлин и в Карловы Вары (положение в ЧССР вызывало в это время уже некоторое беспокойство, и Брежнев хотел провести консультации с В. Ульбрихтом и А. Новотным), Брежнев включил в состав официальной советской делегации не Суслова, как предполагалось ранее, а Шелепина. Октябрьский Пленум ЦК был еще слишком памятным событием, и Брежнев хотел обезопасить себя от всяких «случайностей». После возвращения в мае Шелепин заболел, и с диагнозом «аппендицит» его положили для срочной операции в Кремлевскую больницу. Именно в эти дни Брежнев и решил собрать заседание Политбюро для смещения В. Семичастного. В одной из недавно опубликованных статей П. Е. Шелест так описывает эту политическую операцию:

«18 мая 1967 года я приехал в Москву на заседание Политбюро.