Состоявшийся в августе 1955 года пленум ЦК Компартии Казахстана избрал первым секретарем ЦК КП Казахской ССР Л. И. Брежнева. Разумеется, главной заботой Брежнева и после этого нового назначения оставалась целина. Распашка новых земель резко сократилась, но на уже распаханных 20 миллионах гектаров шла напряженная подготовка к посевным работам 1956 года. Пережить новую неудачу на целине и Брежневу, и тем более Хрущеву было бы очень трудно.
Наиболее близким для Брежнева человеком, личным другом становится в это время Динмухамед Ахмедович Кунаев, Председатель Совета Министров Казахской ССР. Вместе с ним Брежнев в феврале 1956 года возглавил группу делегатов от Казахской ССР на XX съезде КПСС, который резко изменил не только политическую атмосферу в стране и партии и состав ЦК КПСС, но и личную судьбу Брежнева.
Он выступал на четвертом заседании съезда как партийный руководитель Казахстана. Брежнев активно поддержал все начинания ЦК КПСС и лично Н. С. Хрущева, особенно отметив укрепление в стране «государственной социалистической законности, которая была, как известно, ослаблена, а в некоторых звеньях подорвана врагами партии и народа». И обещал довести производство зерна в республике до 1 миллиарда 400 миллионов пудов уже в 1956 году и затем увеличивать его по мере роста урожайности.
Целина действительно порадовала всю страну осенью 1956 года небывалым урожаем. Но Брежнев находился в это время уже не в Казахстане. На первом после съезда Пленуме ЦК КПСС он был избран кандидатом в члены Президиума и одним из секретарей ЦК. Он остался в Москве, и его новая работа была мало связана с проблемами сельского хозяйства.
Теперь он должен был контролировать развитие тяжелой промышленности, капитального строительства, космонавтики, работу оборонной промышленности.
Как и целина, космонавтика стала одним из главных пристрастий Н. С. Хрущева. Он лично занимался всеми ее главными и многими мелкими проблемами и принимал здесь все наиболее важные решения. Но Хрущев был главой государства и партии, и для повседневной работы в новой области ему нужен был верный и послушный помощник. Неудивительно, что после целинной эпопеи выбор Хрущева пал на Л. И. Брежнева.
Бурные события 1956 года: волнения в Грузии, волнения рабочих в Польше, восстание в Будапеште, война за обладание Суэцким каналом между Англией и Францией с одной стороны и Египтом — с другой и другие — мало затронули внимание и время Брежнева. Но ему приходилось нередко заменять Хрущева при решении не только сложных проблем промышленности, но и сельскохозяйственных, в частности целинных, проблем. С большим напряжением шли работы и по созданию нового поколения советских ракет, способных как запускать в космос мирные спутники, так и нести через моря и океаны ядерные заряды.
В своих воспоминаниях, рассказывая о развертывании космонавтики, Брежнев упоминает о множестве людей и событий, но ни разу не называет имени Н. С. Хрущева. Создается впечатление, что в 1956–1960 годах все главные решения по линии ЦК КПСС в области космонавтики принимались в кремлевском кабинете Брежнева. Несомненно, Брежнев во многих отношениях помог в эти годы развитию космонавтики. Но не следует и преувеличивать его действительной роли и реального вклада.
В 1957 году обстановка внутри Президиума ЦК КПСС обострилась, и все новые предположения Хрущева, и в первую очередь о реорганизации управления народным хозяйством, встречали сопротивление и критику. Постепенно противники Хрущева объединились и, наконец, бросили ему вызов на заседании Президиума ЦК 18 июня 1957 года. Хрущев оказался в меньшинстве. Но почти все кандидаты в члены Президиума, и в том числе Брежнев, твердо стояли на его стороне.
Брежнев не привык к подобного рода острым столкновениям, он временами казался растерянным, и, как рассказывают, после одной из грубых выходок Кагановича у него случился обморок. Но в итоге Хрущев одержал полную победу. А Брежнев стал членом обновленного Президиума ЦК.
1958 и 1959 годы прошли для Брежнева в основном спокойно, и его восхваления Н. С. Хрущева на внеочередном, XXI съезде КПСС были искренними. В эти годы Брежнев несколько раз выезжал за границу, главным образом на съезды коммунистических партий некоторых стран. Влияние его росло, и вряд ли можно считать случайным, что как раз в 1956–1960 годах некоторые из его прежних близких соратников из Молдавии, Украины и Казахстана стали перебираться на работу в Москву.