1963年暮春，弗洛尔·科兹洛夫中风，赫鲁晓夫开始考虑其身后事。科兹洛夫是一个颇有争议的人，曾一度被视为赫鲁晓夫潜在的接班人。但是，他只有55岁，却得了一场大病，而赫鲁晓夫已经69岁，这让赫鲁晓夫颇为忧虑。“我老了，”听到消息后，赫鲁晓夫对儿子说道，“主席团其他委员都能当祖父，要退休了。我进政治局时才45岁。那个年龄最适合处理国家大事。你有精力，你还有许多时间。”
赫鲁晓夫一直在考虑将来某个时候退休的问题。1959年首次访美时，他向随行人员披露，他不想仿效列宁、斯大林，像他们一样死在办公室。这让人大吃一惊。“让一个人干到死，那是不可能的。”赫鲁晓夫说，“如果连资产阶级和资本家都不害怕总统任满两届后其政权基础会受到动摇，那我们为什么要害怕呢？”
但是，69岁的赫鲁晓夫身体健壮，尚未考虑过要在1963年马上退休。他告诉儿子，想工作到苏共23大召开，还有两年多的时间。除和肯尼迪实现缓和外，1963年，赫鲁晓夫还在国内实施经济改革。年初，米高扬反对解散其家乡高加索地区的国有大型工业集团，针对此，他大力推进苏联工业的大规模重组。赫鲁晓夫尤其有理由想在一段足够长的时间内来观察他曾在化学工业投下的巨资是否会有回报。20世纪50年代中期，赫鲁晓夫大力倡导生产化肥，这是他强调重视棉花生产的结果。一流的化学工业将保证苏联生产出大量的化肥，以人造化肥来替代生物肥料，从而改进粮食生产，提高纺织原料的产量。
1955年以来，在外交政策方面，赫鲁晓夫缺少了一种似曾相识的外交使命。中苏关系已经取代了超级大国间的斗争，成为克里姆林宫面临的最大外交难题。到1963年秋，他和美国的关系已进入一个平稳时期。9月30日，美国还想再打通一个秘密联系赫鲁晓夫的渠道。肯尼迪向克里姆林宫推荐他的新闻秘书皮埃尔·塞林杰，启动与克格勃驻华盛顿情报站的G.V.卡波维奇上校的秘密会谈。
11月22日肯尼迪在得克萨斯的达拉斯被刺身亡之时，塞林杰和卡波维奇间的秘密联络渠道尚未建立起来。此事对赫鲁晓夫有很大的刺激，他有理由来面对人类不可改变的死亡问题。一听到肯尼迪被刺杀的消息，赫鲁晓夫就认为这是一场阴谋。克格勃千方百计想找到右翼军国主义分子和石油巨头策划这场阴谋的证据，但还不能把克里姆林宫牵涉其中。赫鲁晓夫并不会因为缺乏证据而因此打消他内心深处对美国社会的怀疑。10年来，和美国人的多次谈判，乃至几次峰会，都未改变他的基本看法：美国人分为两类。肯尼迪代表较好的一类美国人，尽管他们反苏，但谨慎小心，有一定的进步性，而且反对战争；另一类美国人好斗而且唯利是图。赫鲁晓夫把后一类美国人视为敌人。现在的事实让他相信，是那些邪恶的美国人杀死了肯尼迪。
赫鲁晓夫来到美国驻苏大使馆，并在吊唁簿上签字，以此来表达对这位年轻美国领导人去世的关心。米高扬代表赫鲁晓夫和苏联参加了肯尼迪的葬礼，并会见了美国新总统林登·约翰逊。
肯尼迪的死再次提醒赫鲁晓夫，他在对外关系上取得的显著成功还很脆弱。1963年底和1964年初，他再次尝试改善和中华人民共和国的关系，但是，却无任何进展。共产党执政以前，两国就存在着边界纠纷问题，现在，中苏两国再次发生边界纠纷。1964年1月，赫鲁晓夫向大多数国家的领导人发送了他准备的一份通告，呼吁和平解决边界纠纷。中国对此置之不理，两国之间也未就边界纠纷进行谈判。莫斯科还见证了和北越关系的冷淡，后者不但追随中国，而且厌恶莫斯科愈益明显的对东南亚共产主义斗争不干涉的政策。
赫鲁晓夫继续在世界各地寻找朋友。5月，他出席了埃及阿斯旺大坝的合龙仪式。6月，他又来到斯堪的纳维亚。合龙仪式标志着近10年来赫鲁晓夫的努力使苏埃关系取得了建设性成果，但它也暗示着苏联对外政策在这一地区的失败。赫鲁晓夫发现邻座是伊拉克的反共领导人阿里夫，但他只能保持冷静。与埃及人私下的交谈中，苏联代表团提及纳赛尔迫害埃及共产党员这个尴尬的话题。“一个建设社会主义的国家为何要实施反共政策？”苏联人问道。然而，赫鲁晓夫从中东回国后，却对苏联能在那里继续扩大其影响充满信心。5月26日，他给主席团的报告称，纳赛尔打算帮助苏联解决阿里夫的问题。陪同赫鲁晓夫出访的苏联外交部长葛罗米柯则指出，纳赛尔是个“复杂的政治人物”，“在一系列问题上，可能都很强硬，但他试图要理解我们的看法”。赫鲁晓夫仍然告诫大家，未来是否会有所收获取决于克里姆林宫如何更巧妙地回应阿拉伯的民族主义思潮。当地的共产党员，如叙利亚共产党的领导人哈立德·巴格达什责骂阿拉伯的统一，他们把阿拉伯的统一视为反对社会主义革命的行为。虽然莫斯科对民族主义情结颇为同情，但从埃及回来后，赫鲁晓夫还是认为，莫斯科在中东地区需要更加务实。“若支持反对阿拉伯民族主义的提法，”他说，“我们将找不到解决阿拉伯地区问题的办法……我们没有理由来反对阿拉伯的统一。统一问题应该展开。”苏联领导人相信，莫斯科应该更多地考虑介入中东事务。他认为纳赛尔确实是进步人士，这个地区再无像他这样的领导人。意识形态并非吸引他的唯一因素。赫鲁晓夫的竞争天性暴露出来，一回国就准备建议克里姆林宫应向阿拉伯人出售武器。如果莫斯科不介入更多的中东事务，他告诫主席团委员，“中国人或许会介入”。
中国不是赫鲁晓夫最大的政治威胁，然而，当他出访外国时，一些主席团委员开始联合起来反对他。根据许多研究者的说法，这些人之所以反对他，既不是因为和华盛顿建立的关系毫无意义，也不是因为和北京形成的对抗关系。赫鲁晓夫在克里姆林宫独断专行，导致他失去了人们的支持。
教育问题，尤其是苏联小学的学制问题，让人们对他的反对公开化。为了把普通教育与自主思考密切结合起来，赫鲁晓夫准备把苏联的学制限制在8年。1958年，他把矛头对准了彻底改革苏联教育的问题。为减少他所称的游手好闲者，赫鲁晓夫号召，在现有10年义务教育的基础上再增加一年学习时间，这一年主要在假期接受教育。苏联学生每周要抽出两天时间去工厂做工。6年后，赫鲁晓夫认为这个试验失败了。但是，他并未决定废除假期做工、增加一年的科学和文科教育学时的制度，而想压缩苏联学生的课堂学习时间。
计划引起主席团的一致反对。这一问题的讨论始于1963年12月，一直持续到1964年7月。矿工出身的米高扬认为，苏联需要更多能和美国展开竞争的科学家，他反对赫鲁晓夫的主张，而后者很害怕这种反对被扩大到苏联的知识界。在类似的讨论中，赫鲁晓夫以正统的马克思列宁主义者自居，极力反对智力教育。“那些支持11年学制的人，其政治倾向是错误的。”1963年12月，赫鲁晓夫说道。他想让苏联年轻人在完成8年的学习后就开始工作。“主要问题是让这些学生工作。”这是赫鲁晓夫一贯的看法。尽管一再坚持，但7月30日的主席团会议并未就此作出决定。
8月，当赫鲁晓夫单方面宣布废除苏联11年学制后，他的麻烦又来了。因为主席团仍未就教育改革作出决定，这一行为表明，他毫不在乎苏联的一套议事程序。即使在其权力巅峰之际——古巴导弹危机之前，他都尊重主席团以多数投票来作出决定的程序。到1964年，反对赫鲁晓夫的力量已经集聚起来，这股力量很大，以至于这次他们不会再原谅赫鲁晓夫的鲁莽行为。
苏联最高苏维埃主席团主席列昂尼德·勃列日涅夫挑起了要让赫鲁晓夫下台的阴谋，这赢得多数人的支持。勃列日涅夫也出生于乌克兰，曾是赫鲁晓夫的亲信，比后者年轻10岁。1960年就任最高苏维埃主席团主席以来，其地位陡然升高。和赫鲁晓夫一样，勃列日涅夫对导弹和空间技术也很着迷，而且，主席团一度还让他就此问题提交过报告。最近，他郑重宣告，苏联在空间技术发展方面首屈一指。和他站在一起的是1960年以来成为主席团委员的尼古拉·波德戈尔内。和勃列日涅夫一样，波德戈尔内也是赫鲁晓夫提拔的。
为赢得秘密情报机构的支持，勃列日涅夫求助于亚历山大·谢列平。后者为中央委员会书记，1961年前曾任克格勃主席，而且仍与克格勃保持着特殊关系。谢列平不需要劝说，和其他人不同——他们对赫鲁晓夫国内政策的失败颇为不满，而谢列平之所以决心要把赫鲁晓夫赶下台，是出于对其对外政策的不满，尤其对刚刚与美国达成缓和的策略不满。谢列平认为，向美国妥协充其量是一种临时性策略，而赫鲁晓夫要全面放弃军事竞争，对他来说，这似乎是白日做梦。对赫鲁晓夫改变苏联对外政策以适应第三世界民族主义政权的行为，他也颇为不满。谢列平不同意赫鲁晓夫的乐观看法，即后殖民地时代的政权将始终服务于莫斯科，在更广范围内传播共产主义的利益。
赫鲁晓夫出访埃及或许是谢列平反对他的导火索。谢列平认为，赫鲁晓夫付出很多，而第三世界反对共产主义的那些国家领导人却并不喜欢他，结果，他让苏联丧失了尊严。赫鲁晓夫竟然和伊拉克阿里夫那样的人共同出席仪式，这让他更加厌恶赫鲁晓夫。
谢列平也不同意赫鲁晓夫对待北京的策略。他把毛泽东视为威胁，并把与河内发生的争吵归咎于赫鲁晓夫，那不是因为莫斯科处理与北京的关系方面犯了错误，而在于赫鲁晓夫一心想着要和美国在老挝达成妥协。
谢列平能得到其门生弗拉基米尔·谢米恰斯内的支持，后者在1961年取代他出任了克格勃主席。谢米恰斯内欠了赫鲁晓夫的账，但他欠谢列平的更多。求助于克格勃并不只是因为谢列平高升后把自己原来的职位交给了谢米恰斯内。后者此前先是谢列平的副手，然后才步其后尘出任共青团中央书记。两人都是苏联新一代行政领导人的象征——都出身于“共青团派”。在1960年代，这些斯大林时代的领导人都垂垂老矣，他们要把指挥棒交给年轻的“共青团派”。
1963年的某一天，勃列日涅夫、波德戈尔内和谢列平开始利用赫鲁晓夫不在莫斯科的时机策划这个阴谋。零零散散的资料表明，这个阴谋小集团在决定怎么做才能把赫鲁晓夫赶下台这个问题上，颇费了一番周折。1964年春的某一天，勃列日涅夫想让谢列平和谢米恰斯内考虑暗杀赫鲁晓夫：乘其出国访问之机，制造一起空难事故。他们一度还策划乘赫鲁晓夫访问斯堪的纳维亚期间实施这一方案。最后，方案落空。阴谋集团扩大后，主要的几个阴谋家有理由相信，在中央委员会投票时赫鲁晓夫会输。
值得注意的是，这场阴谋策划了数月之久而赫鲁晓夫却浑然不知。刚从埃及回来时，赫鲁晓夫的儿子首先听到了一丝风声。中央委员尼古拉·伊格纳托夫的前侍卫长向赫鲁晓夫的儿子谢尔盖透露，说他的顶头上司正在全国游说，招募同党来解除赫鲁晓夫的职务。提供消息的瓦西里·加柳科夫称，阴谋集团成员有谢列平、勃列日涅夫和波德戈尔内，且声称，他们已谋划多日，准备在10月动手，正值11月中央全会召开之前。
赫鲁晓夫对此置之不理。“当我把加柳科夫透露的消息告诉父亲时，他又信又不信。”谢尔盖·赫鲁晓夫后来回忆道。赫鲁晓夫仍然对自己牢牢地控制党和国家充满信心。1957年，曾挫败过企图夺权的阴谋，而且，他不相信现在还有人能组织起反对他的阴谋活动。“勃列日涅夫、谢列平和波德戈尔内不是一类人……无稽之谈！”
赫鲁晓夫唯一可以求助的人就是老战友米高扬。古巴危机以来，他们的关系得到改善。1962年，当卡斯特罗似乎一心想要对美国人和苏联人开战时，米高扬以高超的手法妥善安抚了古巴人，对此，他充满感激之情。现在，更重要的是米高扬自己也对赫鲁晓夫充满敬意。1962年10月，两人有关潜艇问题的争吵已经被忘却。1963年6月，赫鲁晓夫决定结束其不切实际的柏林政策，对米高扬来说，这意味着苏联的对外政策正在走上正确的轨道。5年来，在支持赫鲁晓夫与西方妥协的同时，米高扬一直在内部进行着斗争，以抑制赫鲁晓夫桀骜不驯的本性。赫鲁晓夫要求米高扬见见那个侍卫长加柳科夫，看看那个消息是否准确。
赫鲁晓夫要让那些阴谋家知道，他也在观察他们。他与波德戈尔内正面接触过，对方马上矢口否认。毫无疑问，不出几个小时，谢列平和勃列日涅夫就会知道此事，他们要么加快步伐，要么放弃。
看到父亲对此消息毫无反应，谢尔盖·赫鲁晓夫很失望。他发现父亲的举止“非常古怪，不合逻辑，而且令人费解”。有人搞阴谋的传言并未改变赫鲁晓夫10月初到皮聪达休假的计划。唯一的变化是，他请米高扬在和加柳科夫会面后到他那里去。
这位苏联领导人相信，他能粉碎反对派的任何阴谋。如果米高扬给他出过主意，还不清楚他到底提了哪些建议。米高扬后来的行为清楚地表明，他曾建议赫鲁晓夫至少放弃一个职位，以此来保证其外交政策的连续性。
