В 1957 году обстановка внутри Президиума ЦК КПСС обострилась, и все новые предложения Хрущева, и в первую очередь его предложения о реорганизации управления народным хозяйством, встречали сопротивление и критику. Постепенно противники Хрущева объединились и наконец бросили ему вызов на заседании Президиума ЦК КПСС, начавшемся 18 июня 1957 года. Среди членов Президиума Хрущев оказался в меньшинстве. Но почти все кандидаты в члены Президиума, и в том числе, конечно, Брежнев, твердо стояли на стороне Хрущева. Брежнев не привык к подобного рода грубым столкновениям, временами он казался растерянным, и, как рассказывают, после одной из грубых выходок Кагановича у Брежнева случился обморок. Но в итоге острого политического столкновения Хрущев одержал победу. Из Президиума ЦК КПСС были выведены В. М. Молотов, Г. М. Маленков и Л. М. Каганович, а затем также М. З. Сабуров и М. Г. Первухин. В то же время численность Президиума ЦК была увеличена до 15 человек, и в его состав вошли почти все недавние кандидаты: Л. И. Брежнев, Е. А. Фурцева, Ф. Р. Козлов, Н. М. Шверник, Г. К. Жуков. Среди девяти кандидатов в члены Президиума появились имена А. Н. Косыгина, А. П. Кириленко и К. Т. Мазурова. Таким образом и для этих людей июньский Пленум ЦК КПСС стал важным этапом их политической карьеры.

1958 и 1959 годы прошли для Брежнева в основном спокойно, и его восхваления в адрес Хрущева на внеочередном XXI съезде КПСС были искренними. В эти годы Брежнев несколько раз выезжал за границу, но главным образом на съезды коммунистических партий других стран. Влияние Брежнева увеличивалось, и вряд ли можно считать случайным, что как раз в 1956–1960 годах некоторые из его прежних близких соратников из Молдавии, Украины и Казахстана стали перебираться на работу в Москву.

Одним из первых начал работать в аппарате ЦК КПСС Г. Э. Цуканов. Он возглавил пока еще небольшой личный секретариат Брежнева, которому нужны были помощники для работы и в ЦК КПСС, и в Бюро ЦК КПСС по РСФСР. Цуканов стал с 1958 года главным личным помощником Брежнева и оставался таковым до его смерти. Еще раньше – в 1956 году – переехал из Кишинева в Москву К. У. Черненко. Непосредственно в аппарате Брежнева для Черненко не было подходящей должности, и он стал работать в одном из секторов Отдела пропаганды ЦК КПСС, а также в редакционной коллегии журнала «Агитатор». В качестве инструктора Отдела агитации и пропаганды ЦК КПСС стал работать и приехавший в Москву С. П. Трапезников. Разумеется, Брежнев нередко встречался и укреплял связи с теми из своих друзей, сокурсников, сотрудников, товарищей военной поры, которые уже раньше работали в Москве в самых различных учреждениях. Я имею в виду таких людей, как генерал Г. К. Цинев, который с 1954 года работал в КГБ; как Н. А. Тихонов, который еще в 1950 году стал начальником одного из управлений в Министерстве черной металлургии, а в 1957 году возглавил Днепропетровский совнархоз. На ответственных постах в Москве продолжали работать и такие друзья Брежнева, как К. С. Грушевой и П. Н. Алферов. Брежнев любил приглашать всех этих людей по разным поводам в свою большую квартиру в доме № 26 на Кутузовском проспекте.

После июньского Пленума ЦК КПСС Хрущев сконцентрировал в своих руках почти неограниченную власть. Он был не только Первым секретарем ЦК КПСС. С весны 1958 года Хрущев занял также пост Председателя Совета Министров СССР. Однако при всей покорности К. Е. Ворошилова Хрущева раздражало, что этот недавний активный участник «антипартийной группы» продолжал оставаться Председателем Президиума Верховного Совета СССР. В мае 1960 года было решено торжественно проводить Ворошилова на пенсию. На его место Хрущев предложил избрать 53-летнего Л. И. Брежнева.