“有一次在巴维哈，”外交部副部长谢苗诺夫回忆说，“葛罗米柯邀约我散步，第三人便是列·伊·勃列日涅夫。他当时还年轻、漂亮，在女人面前颇获成功（这是护士们对我说的）。我们走过了大约六公里，勃列日涅夫一路上都在讲述与马林科夫、布尔加宁等人的小集团斗争期间他的一些个人感受和工作。在他对赫鲁晓夫的评价中，隐隐透露出批评的意味，尽管他们当时还站在一起。这个热情、坚毅的人令我很感兴趣，不过当然我无法想象后来他摇身一变的情形。”
全会之后，赫鲁晓夫委托勃列日涅夫处理一些极为重要的问题——军事工业、火箭制造、宇宙航行。勃列日涅夫与宇宙火箭系统的总设计师们建立了良好的关系，这些人各有各的复杂性格。如若遇到与勃列日涅夫意见不合的情况，他们可以径直去找赫鲁晓夫。不过他们接纳了勃列日涅夫，在赫鲁晓夫主政时期将其视作自己的代表。
赫鲁晓夫愈来愈信赖自己所提拔的这个人。1957年7月他和政府首脑布尔加宁出访捷克斯洛伐克。他们不在期间即由勃列日涅夫主持中央主席团会议。
1957年10月赫鲁晓夫将国防部长朱可夫元帅撤职之时，勃列日涅夫是最早表态反对朱可夫的人之一，他愤怒地指责朱可夫在军队中搞个人崇拜。顺便说说，他成为国家元首之后，也没有改变对朱可夫的否定态度。
1956年2月27日，中央全会决定建立苏共中央俄罗斯联邦局——“目的在于更加具体地领导共和国党组织、各州和边疆区的苏维埃机关、经济机关的工作，更加及时有效地解决俄罗斯苏维埃联邦社会主义共和国的经济和文化建设问题”。俄罗斯局机关内设立六个部：党的机关部，工业和交通部，农业部，行政和财政贸易部，宣传鼓动部，科学、教育和文化部。
赫鲁晓夫被任命为中央委员会俄罗斯联邦局主席。1958年1月3日的主席团会议上，勃列日涅夫被批派为联邦局副主席。他受命分管俄罗斯的党务干部和工业。
1958年3月25日，赫鲁晓夫最终决定甩掉仍是政府首脑的自己先前的战友布尔加宁。当即有人提出任命赫鲁晓夫担任这一职务的建议。
“不可能有别的建议，”勃列日涅夫指出，“赫鲁晓夫同志就任部长会议主席职务必将难以估量地提高政府的威信。他一定会对国家的对外政策贡献出自己的天才。”
4月17日，中央主席团会议决定设立直属苏联国防委员会的分管原子弹、氢弹和导弹武器的军事科技委员会。任命赫鲁晓夫为主席，勃列日涅夫为副主席。苏联核武器的主要创始人——哈里顿和萨哈罗夫两位院士，曾向勃列日涅夫求助。他们担心政府正在酝酿一项从他们的观点看来不正确的决定。
萨哈罗夫院士讲述道，“勃列日涅夫在他小小的新办公室接待我们，办公室就在我曾经见过贝利亚的那幢大楼里。”
当院士们出现之时，勃列日涅夫高声叫道：
“啊，扔炸弹的人来啦！”
勃列日涅夫笑呵呵地说，他的父亲把那些制造新式杀人武器的人看作坏蛋，还说应当把这些坏蛋带到大山上，让大家眼看着绞死。
“如今我自己也在干这种黑心事，不过和你们一样，都是怀着美好的目的。”勃列日涅夫说。
他仔细听取院士们的意见，在白纸簿上记了一些，最后总结道：
“我完全明白你们的意思，一定和同志们加以商量。你们会知道结论的。”
他接受了院士们的意见。部长会议的决定未能通过……
政治局委员沃罗特尼科夫，曾经回忆过勃列日涅夫去古比雪夫“进步”工厂的情形。这是一间19世纪末建成的工厂，即当年的莫斯科“杜克斯”自行车厂，革命后更名为国营第一航空厂，战争期间疏散到古比雪夫。该厂生产飞机，最新的一架为图-16战略轰炸机。1957年末奉命生产首枚由科罗廖夫设计的洲际弹道导弹。
勃列日涅夫在车间里与工人们交谈，给大家留下了良好的印象。身材匀称，面带微笑，喜欢交往，烟斗里吸着一成不变的小雪茄，勃列日涅夫很容易接近，不过也有一点儿装腔作势。他对工人们提出的尖锐问题全都耐心地一一作答。自己也对业务工作提了一些问题。
1959年12月14日的中央主席团会议上，赫鲁晓夫热情洋溢地讲述了他心目中的苏共新纲领是何种情形。15—20年内应当建成共产主义社会。苏维埃政权已经建立，现在还应该干什么呢？保障退休人员安度晚年，让孩子们上寄宿学校。还要确保官员定期更替，以免在高级职位上待得太久。
“我完全同意这些建议，”勃列日涅夫说，“尼基塔·谢尔盖耶维奇的建议是列宁关于国家学说的进一步发展。人民和党一定会欣然接受这个纲领。共产主义的明显特点是将会获得现实的感觉得到的内容——寄宿学校、免费教育、养老保障、食品日常消费进一步增加。应当支持尼基塔·谢尔盖耶维奇的建议……”
作为哈萨克的前任领导人，勃列日涅夫一直关注该共和国的状况。他不得不为发生在共和国的危机操劳。
1958年12月在莫斯科举行中央全会。哈萨克领导人雅科夫列夫和库纳耶夫被召到主席团房间。赫鲁晓夫二话不说便明言，中央委员会要派别利亚耶夫去哈萨克，建议让他担任第一书记职务。
别利亚耶夫原在阿尔泰工作，1955年赫鲁晓夫亲自将其带到莫斯科，让其担任苏共中央书记。但赫鲁晓夫很快便对自己所提拔的人感到失望，决定将其从首都调往共和国。
“嗯，雅科夫列夫就当第二书记好了，”赫鲁晓夫最后说道。“全会对组织问题需要以高度的组织纪律性进行解决。”
库纳耶夫答应一切照办，但雅科夫列夫不想出任那里的第二书记，因为刚才还是第一书记。他说希望离开共和国，于是被派往乌里扬诺夫斯克任第一书记。1961年他从乌里扬诺夫斯克调往鄂木斯克，职务大降——仅任市执委会主席。
同时，被派往哈萨克的别利亚耶夫也不走运。1959年哈萨克庄稼绝收，播种的作物被一场早雪严严覆盖。共和国承诺上交9亿普特粮食，仅仅交了7亿。而更不愉快的事情还在后头。1959年8月1日在铁米尔市，卡拉甘达联合企业的建设者因生活条件恶劣而拒绝出工。
莫斯科赋予这个项目以特殊意义，它为开发巨大的卡拉甘达煤田创造了机遇。大批年轻工人凭共青团的介绍信从全国各地涌向该市，却无法安置他们，况且也还没有工作可干。
年轻人们不知该做什么。15000人在军用帐篷中栖身，伙食又很糟糕。在哈萨克草原特别的酷热天气里，又缺少饮用水。烈日下的贮水槽中，冷水变成了开水。
8月1日晚上，一伙年轻人砸坏锁子，喝光了停在食堂附近的槽车中的克瓦斯。总的看来，工人们确实备受酷暑折磨，却没有地方可供消暑。从这个小插曲开始，随后演变成一场被定性为流氓行为的事件——人群冲进食堂，有人打开了售货亭。不过后半夜民警到来之后，人们顿时安静下来，一哄而散。
本来到此一切都可能结束，但民警扣留了两个小伙子（后来查明，他们根本与流氓行为无关）。数小时之后扣人事件激发起一场在“释放我同志！”的口号下实施的大洗劫。
市内发生大规模的骚乱，年轻人们以烧酒壮胆，抢劫和焚烧商店，占领内务部边疆区分局大楼，攻击应召前来维持秩序的民警和士兵。
勃列日涅夫赶赴该市。
“我很喜欢勃列日涅夫在那些天所表现的坚定决心，”库纳耶夫回忆说，“他毫无畏惧地出现在一群骚乱肇事者中间，镇定自若地对他们讲话。叫喊和喧哗声寂静下来，终于可以进行交谈了。”
实际上，恢复秩序的是军队的和民警。勃列日涅夫允许动用武器镇压骚乱。为此耗时三天，11人丧生，另有5人由于伤重后来在医院死去。42人被交付审判，百余名官兵负伤。
1959年9月25日，中央主席团会议分析研究卡拉甘达冶金联合企业工地的形势。
别利亚耶夫、库纳耶夫、卡拉甘达州委第一书记伊萨耶夫和哈萨克冶金建设公司经理维什涅夫斯基也应召前来。伊萨耶夫于1958年调入哈萨克升任此职——他原来担任斯维尔德洛夫斯克州委第二书记。
会上苏斯洛夫语带威胁地说，“这起刑事对抗行动具有政治色彩”。大家指出了共和国领导人别利亚耶夫的错误。但他不承认自己有过错。于是最终的决定被推迟，直到10月2日采取组织措施了。
州委第一书记伊萨耶夫被撤销职务，留党察看一年，按照处分程序被任命为伊谢季河上游冶金联合公司热工车间领班。卡拉甘达国民经济委员会主席阿尼克被开除出党，撤销工作。哈萨克内务部部长卡贝尔巴耶夫被撤职。
索洛缅采夫被任命为卡拉甘达州委第一书记，他此前是车里亚宾斯克国民经济委员会的领导人。
苏共中央的决定中载明，哈萨克领导人“对事件未作出深刻的评判，未得出必要的结论，也未采取补救既有局面的措施”。这对共和国领导人别利亚耶夫是不祥之兆。他很迟了才意识到，不立即承认自己的过错是枉费心机。
1960年1月7日，勃列日涅夫在主席团会议上报告了中央书记处分分析研究哈萨克局势的结果。也让别利亚耶夫发了言。他认错悔过：
“勃列日涅夫同志所提出的批评意见是正确的。看来我还不够富有远见的活动家的资格。请大家相信，我已经尽力而为，全身心地投入工作。不过，显然未能让同志们团结一致……我同意组织的结论。”
应召参加会议的哈萨克共产党政治局委员们，都将全部过错推卸到别利亚耶夫身上。随后便让他们离开了，而主席团委员们在小范围内开始讨论干部问题；谁顶替别利亚耶夫，谁可以派去阿拉木图加强共和国的领导。
赫鲁晓夫对别利亚耶夫说：
“我们重新评价过了，你有点粗鲁，需要更加灵活的智慧。”
别利亚耶夫被任命为斯塔夫罗波尔边疆区委第一书记。
该派谁去哈萨克斯坦呢？
勃列日涅夫再次成为候选者：他可是十分熟悉哈萨克的情况。同事们也乐得减少一个强有力的竞争对手。但赫鲁晓夫不想放走勃列日涅夫。
勃列日涅夫利用这一机会，让库纳耶夫在阿拉木图掌握大权。他早就对库纳耶夫怀有好感。1957年11月库纳耶夫曾经飞赴莫斯科看望勃列日涅夫。一番交谈之后，勃列日涅夫友好地问道：
“明天想去克里姆林宫参加招待会吗？中央委员会设宴招待参加共产党和工人党代表国际会晤会议的人员。那里都是国际共产主义运动的精英。”
对库纳耶夫而言，克里姆林宫招待会是一件令人欣喜的大事。当全体来宾齐集之时，赫鲁晓夫出现了。库纳耶夫夫妇被安排与勃列日涅夫的妻子维多利亚同坐一席。他们的席位后面是阿尔巴尼亚领导人霍查和谢胡。
1960年1月9日，勃列日涅夫飞赴阿拉木图参加全会，会上他严厉地批评别利亚耶夫，将库纳耶夫扶上了哈萨克第一书记的交椅，于是库纳耶夫便成为他的忠实战友。
库纳耶夫也未能保住自己的职位。将近两年后，赫鲁晓夫吩咐将哈萨克的几个区划归相邻的乌兹别克斯坦和土库曼斯坦，他表示反对。赫鲁晓夫便下令撤掉这位不肯听话的领导人。
12月24日科兹洛夫飞抵阿拉木图。无论在机场还是汽车上，他都绝口不谈公事。稍事休息后便驱车前往共和国中央委员会大厦。他向政治局委员们说明：
“中央主席团认为，任命库纳耶夫同志为共和国部长会议主席是适宜的。我们推荐尤苏波夫担任第一书记，索洛缅采夫担任第二书记。请支持我们的建议。”
沃罗诺夫曾经讲过1960年勃列日涅夫召见他的情形：
“已经批准你为垦荒边疆区委第一书记并兼任哈萨克中央第三书记。”
“怎么能这样呢，为什么谁都没有向我提起过，也不征求我的意见？”沃罗诺夫不知所措。
“决定已经通过了，”勃列日涅夫坚定不移地说，“你这就坐车去福努科沃，乘飞机到哈萨克斯坦参加全会。”
沃罗诺夫出了门，在走廊里遇见一位中央书记伊格纳托夫，向其抱怨说，决定他的命运却连问也不问他一声。
伊格纳托夫困惑不解地瞧了瞧他：
“主席团会议上波利扬斯基和勃列日涅夫都说你同意呀。”
“谁也没和我说过。”
伊格纳托夫很喜欢给同事使绊子：
“到我办公室去，给赫鲁晓夫打电话。”
沃罗诺夫向第一书记申述：
“尼基塔·谢尔盖耶维奇，我是奥伦堡州委副书记沃罗诺夫。我在奥伦堡的事情很多，还想在那里再工作两三年。”
“不是说你已经同意了吗？”赫鲁晓夫诧异。
“谁也没有和我说过。”
“告诉勃列日涅夫，让他另找一个候选人。”
沃罗诺夫回头去见勃列日涅夫。勃列日涅夫骂了一句，取消了决定，但从此便记恨沃罗诺夫。
勃列日涅夫颂扬起赫鲁晓夫来绝不比主席团的同事们逊色。而且他干这种事易如反掌。1960年2月1日讨论赫鲁晓夫即将出访法国的事。勃列日涅夫不失时机地建议：
“是否可以这样考虑问题：尼基塔·谢尔盖耶维奇访法的中期，在适当的情况下发表一次演说。”
“我认为这可以办到。”赫鲁晓夫当即响应。
“这会非常有意义，而且作用巨大，”勃列日涅夫兴奋地说，“这将会唤起法国整个工人阶级和全体社会公众。”
外交部长葛罗米柯也支持他：
“列昂尼德·伊里奇说得很对，无论就内容、意义或形式而言，这都会是强有力的一着棋。”
国防部第一副部长科涅夫元帅提出了另一个方案：
“我认为，从战术角度考虑，这类演讲最好在俄罗斯国土上发表，以使人感到背后的力量，觉得这是政府、中央委员会所发出的声明。这会提高您的威望，比面对法国或其他外国听众产生更加强烈的印象。”
但勃列日涅夫固执己见：
“难道尼基塔·谢尔盖耶维奇在联合国没有留下印象？你不记得我们乘车离开机场时，人们向尼基塔·谢尔盖耶维奇纷纷伸出手来的情景吗？不能不考虑到这点。”
赫鲁晓夫说：“我认为勃列日涅夫说得对。”
1960年5月4日，赫鲁晓夫对高层领导人进行大调整。比如说，让担任苏联最高苏维埃主席团主席的伏罗希洛夫元帅退休。
70岁高龄的伏罗希洛夫开会时常常入睡，对外国使节和来宾自作主张地随便说话，由此数次酿成国际风波。决定让伏罗希洛夫致函最高苏维埃，请求解除其职务。他的职位则由勃列日涅夫接替。
7月，伏罗希洛夫退出中央主席团，但仍然是最高苏维埃主席团委员，直至生命的最后一刻。
国家的第二把手
对勃列日涅夫而言，新的任命乃是一次晋升，尽管职务本身并无实权。所有的决议均由中央委员会主席团通过，最高苏维埃只不过使其发生法律效力而已。
然而主席的地位使勃列日涅夫成为举国闻名的人物，他的照片开始在报纸上和新闻纪录片中出现。他喜欢颁发勋章，表示祝贺，举行招待会。勃列日涅夫感到骄傲的是，他曾为首位宇航员加加林颁发金星奖章。
