对于肯尼迪而言，赫鲁晓夫同样也是令人烦恼的挑战。从历史的角度来看，肯尼迪的政绩如何就要看他与这位共产主义世界的领导人打交道的水平了。从他的内心来说，他是会反对一个与他父亲相仿的人的。肯尼迪小时候身体不好，老是生病，然而他的父亲坚持要他超过别的孩子，如果他做不到，就会对他进行嘲讽。约翰·肯尼迪最终超过了他的父亲，不仅成为美国总统，而且还是个喜欢吃喝喧闹的人，颇受女性的青睐。不过，他竭力想成为他父亲希望的那种刚强、具有男子汉气概的领导人，这使得与赫鲁晓夫对抗变得更为重要，使得他起初未能做到这一点时显得更加痛苦，也使得在随后的危机中获胜显得更为关键，至少表面上看来是这样。
在美国大选之后，赫鲁晓夫马上开始对肯尼迪倾泻了大量的试探性建议与意见。11月11日：赫鲁晓夫的朋友与奉承者，乌克兰作家亚历山大·科尔奈丘克告诉阿维利尔·哈里曼说赫鲁晓夫想“重新开始，忘掉U-2事件以及所有后续的周折”。三天后，缅希科夫大使对哈里曼说：赫鲁晓夫希望他和肯尼迪“能沿着罗斯福总统时期两国的关系路线发展下去，当时哈里曼先生是驻苏联大使”。缅希科夫11月16日对阿德莱·斯蒂文森说：赫鲁晓夫想“通过信件与代表进行非正式的讨论”以及不设争论话题的“非正式会谈”，不管是“在这里还是在那里”，这样他可以在总统宣誓就职后“不久”颁布核禁试命令。在其他地方遇到中国“扩张”问题（原文如此）时，虽然莫斯科不能让北京接受“两个中国”，但莫斯科会“乐于帮忙”。哈里曼对此的看法很有趣，他于11月21日告诉缅希科夫说“肯尼迪总统的看法”会更好。唉，哈里曼回答说，当选总统“在他执掌权力之前不会任命任何人去进行会谈”。
“我们能帮助美国新政府做些什么？”外交部副部长瓦西里·库兹奈索夫问肯尼迪的顾问沃尔特·罗斯托与杰罗姆·威斯纳，两人于11月底在莫斯科参加一次关于裁军的会议。罗斯托认为，如果苏联能在夏天释放5月被击落的U-2飞行员，如果达成禁止核试验条约，如果赫鲁晓夫此次“穿着鞋子”来到曼哈顿，那么举行纽约首脑会晤还是有可能的。缅希科夫于12月12日邀请罗伯特·肯尼迪共进午餐。两天后，他敦促哈里曼“尽早”举行秘密的非正式会谈。《纽约时报》前驻莫斯科记者哈里森·萨里布里于12月15日得到了这一消息。“现在不应该再浪费时间了，”苏联大使几次重复说，因为“一年的时间已经过去了”，赫鲁晓夫和肯尼迪必须“在那些不希望苏美签署协议的人有机会采取行动阻拦前”会面。[5]外交官大卫·K.E.布鲁斯也于1961年1月5日从缅希科夫那里得到了同样的信息，并受到了伏特加与鱼子酱的款待，以及再次会面的邀请；第二次的会谈仍是重复着与第一次同样的话题。
对于一个让人看起来对请求特别敏感的人来说，这些请求显得不同寻常。这反映了赫鲁晓夫天生的不耐烦性格，这种不耐烦因为德国与柏林问题又拖延了两年以及国内的农业危机而更加强烈了。然而，他对美国政治的理解并不比他对收成不好的解释强到哪儿去。很显然，在新总统宣誓就职前是不能举行非正式会谈的。即使在正式就职以后，也需要更多的时间来安排并使会谈达成效果，而这显然是赫鲁晓夫所不具备的。
约翰·肯尼迪宣誓就职的当天，赫鲁晓夫打电话给在美国大使馆的汤普森大使，这是以前从未有过的，他将汤普森召到了克里姆林宫。在克里姆林宫二层的办公室里，两人隔着一张长长的、上面铺着绿色台面呢的桌子，赫鲁晓夫显得疲惫不堪，声音沙哑。他已经看过肯尼迪的就职演说了，并认为里面有“建设性的东西”，于是他主动提出释放被击落的U-2飞行员，作为对美国新总统表示友好的姿态。
肯尼迪对此也作出了回应：停止了美国邮政局对苏联出版物的审查，对恢复1960年中断的民航会谈表示欢迎，命令军事官员在他们的讲话中降低反对苏联的论调，以及取消进口苏联蟹肉的禁令。但不管是在正式就职之前还是之后，双方做出的姿态表示还是让人感到有些不祥。
1月6日，赫鲁晓夫在一次为前一年秋天在莫斯科召开的81国共产党会议进行思想研究与宣传的秘密会议上作了报告。与会议结束时发表的妥协性声明一样，他的谈话也是经过慎重权衡的。一方面，与中国的路线一样：世界正逐渐过渡到社会主义；帝国主义无论是在国内还是在国际上都逐渐走向衰落；第三世界正在革命中逐渐壮大。另一方面，赞同苏联式的和平共处：与毛泽东不同，赫鲁晓夫坚持认为核战争将会带来“无法估量的损失”，“数以百万计的人将会在核战争中死亡”。“地区战争”也是不可以爆发的，因为这可能会升级为大规模战争。苏联唯一支持的战争，赫鲁晓夫根据他自身对马克思列宁主义的理解说，就是“民族解放战争”，这同样也是毛泽东的观点。这样的斗争是“神圣”而“不可避免的”，就像阿尔及利亚人民反对法国殖民主义那样。
对于苏联的做法来说，这样的讲话是再平常不过的了。艾森豪威尔也有类似的看法，他曾私下里指出，赫鲁晓夫的强硬讲话通常是强硬行动的替代品，而不是前奏。但是肯尼迪不这么认为。根据小约瑟·M.施莱辛格的说法，“与莫斯科亲善的表示相比，讲话的其他部分所充斥的那种虚张声势的自信［除了拒绝核战争那部分外］，特别是通过反抗、暴动与游击战一定能取得胜利的宣言，让肯尼迪感到更为吃惊”。这位新总统将赫鲁晓夫的讲话看成是“苏联意图的权威表述”，并指示他的高级助手们“仔细阅读、标注、领会并吃透意思”，尽管汤普森大使提醒说这种讲话只是体现了赫鲁晓夫复杂心态的一个方面，但肯尼迪并不以为然。他在1月30日的国情咨文中回击说：“我们千万不能盲目地相信两个大国［苏联与中国］已经放弃了他们统治世界的野心——就在不久前，他们还强烈地重申了这种野心。相反，我们的任务是使他们相信侵略与颠覆并不是追求这些目标的有益道路。”
两天后，美国对它第一枚“民兵”洲际弹道导弹进行了发射试验，媒体报道说，这是美国于1962年中期进行大规模部署的前奏。2月6日，美国国防部长罗伯特·S.麦克纳马拉披露说，赫鲁晓夫一直以来极力鼓吹的苏联导弹优势其实是一种神话。[6]与此同时，赫鲁晓夫有关尽早举行首脑会晤的呼吁仍然没有得到美国方面的正式答复。这并非想直接挑战赫鲁晓夫，但是他并不理解这一点。
私下里，肯尼迪并没有显得像他在国情咨文中所说的那么吃惊——在2月11日与苏联问题顾问会谈后，查尔斯·波伦甚至担心肯尼迪低估了赫鲁晓夫扩张世界共产主义的坚定决心。在国务卿腊斯克看来，肯尼迪总统的吃惊也许可以看成是他急于尽早与赫鲁晓夫举行会晤的表示。“肯尼迪得出印象认为，”腊斯克后来回忆说：“如果他能与赫鲁晓夫坐下来，那么也许会得出一些有益的成果——至少可以就各种问题更亲密地交换看法。”肯尼迪对他的助手肯尼思·奥唐奈尔说的是：“我得让他知道我们可能和他一样强硬。通过其他的人，我是不可能向他传递这种信息的。我得和他坐下来，让他知道他是在和谁打交道。”
在和他的苏联问题顾问——汤普森、哈里曼、凯南与波伦——进行了又一次磋商后，肯尼迪总统批准与赫鲁晓夫“非正式交换意见”，如果国际形势与双方的日程安排允许的话。汤普森大使于2月27日回到莫斯科后将转交肯尼迪给赫鲁晓夫的一封信，并讨论有关会谈的细节问题。根据特罗亚诺夫斯基的说法，与此同时，赫鲁晓夫对肯尼迪的希望却开始“很快地消失了”，他反而玩起了“等待的游戏”，并不“急切回复”美国总统关于会谈与交换意见的提议。
刚果形势的发展并没有给予赫鲁晓夫以帮助，2月13日传来了卢蒙巴被谋杀的消息，赫鲁晓夫谴责这是哈马舍尔特在联合国支持下的“西方殖民主义者”所犯下的罪行。与此同时，西方国家在德国与柏林问题上的拖延仍然继续着。苏联于2月17日给波恩发去了一份备忘录，对一些西方国家领导人的言论提出了抱怨，他们说：“‘等一下，现在时机还不成熟。美国正在准备总统大选。我们必须等到美国大选结束。’在大选结束后，他们又说：‘总统和新的美国政府刚刚履职，还没有进入状态。’……如果事情照这么发展下去，那永远没有解决的时候。”
汤普森于2月27日回到了莫斯科。赫鲁晓夫于第二天早上离开了莫斯科，开始了他的下一轮全国农业视察，并没有接见汤普森大使。汤普森直到3月9日才在诺沃斯比尔斯克赶上了赫鲁晓夫，向他转交了肯尼迪总统的信件。这位苏联领导人当时正呆在西伯利亚科学院像大学校园似的总部里，这里是根据他的命令刚刚修建的。当地的学者发现赫鲁晓夫心情很烦躁。汤普森认为，他看上去“特别疲惫，他的表情甚至让陪同我的苏联人都大吃一惊”，当赫鲁晓夫发现肯尼迪的信中甚至都没有提到柏林问题时，他的心情更加烦躁了。
自从宣誓就职以来，肯尼迪一直努力回避这个问题。汤普森在2月份提醒说，如果在柏林与德国问题上“没有进展”，那赫鲁晓夫“几乎肯定会签署［他的］单独和平协议”，接着东德就可能试图“慢慢钳制”柏林。要想避免出现这种情况，办法就是“在德国问题上采取一些行动，表明在美国大选后是可能取得真正的进展的”。然而，美国总统并没有给赫鲁晓夫这种希望，而是指示汤普森在诺沃斯比尔斯克不要提及柏林问题。如果赫鲁晓夫能保持克制的话，正如汤普森冷静的描述所说的那样，那也是因为他现在已经放弃了从美国这块石头中榨出油来的希望了：“……赫鲁晓夫指出我没有提及他希望讨论的德国问题。他说苏联在给阿登纳的备忘录中已经表明了自己的立场。……他说他已经向艾森豪威尔总统详细阐述了苏联的立场。……他说他非常希望肯尼迪总统会理解苏联在德国问题上的立场。”
汤普森能做出回答的只是总统“正在考虑我们的德国政策，并希望在做出结论前与阿登纳和其他的盟国进行协商”。但是他猜测美国的立场不会有“太大的变化”。他提醒赫鲁晓夫说：“如果有什么事情让美国做出大幅增加军事开支的决定，就像在朝鲜战争时期那样，那肯定是美国相信苏联真的想以武力将我们驱逐出柏林了。……”
几天后，汤普森提醒他的上司们说：“我所有的外交同事们都认为，如果不进行谈判，那赫鲁晓夫今年将会与东德签署独立的和平协议，并触发柏林危机。”他甚至预期柏林墙的“边境通道可能会被封锁起来，以阻止他们肯定会认为的柏林难民的继续流动，这是他们无法忍受的”。双方对他的这些警告都没有给予足够的重视。在只考虑自身优势的情况下，赫鲁晓夫忽视了给肯尼迪所带来的危险。肯尼迪认为经过三年的施压后，赫鲁晓夫也许能接受进一步、无限期的拖延。
4月中旬，美国专栏作家沃尔特·李普曼和他的妻子海伦在皮聪大的别墅里采访了赫鲁晓夫。赫鲁晓夫成功地将严肃的话题穿插在一系列友好的表示中，他们一起散步，打羽毛球（这位肥胖但灵活的总理打败了李普曼），并一起共进了两次丰盛的宴会，他向李普曼夫妇传达的信息是独立的德国和平协议将会是苏联最后的手段。“我不想制造紧张气氛，”他几次说道：“我知道这是会造成紧张的。我想尽力避免。但是最后，我还是不得不去做。”当李普曼说这样可能会有战争的威胁时，赫鲁晓夫宣称：“西方没有哪位愚蠢的政治家会因为我们与德意志民主共和国签署了一个和平条约而发起一场会使数以千万计的人丧生的战争的。……现在还没有这样的傻子，或者这样的傻子还没有出生。”根据华盛顿的指示，李普曼建议在柏林问题上设一个五年的延期处理期限。赫鲁晓夫盯着他，就像他精神不正常似的。一个月后，当汤普森建议让柏林“保持现状”时，赫鲁晓夫发誓说：“事情不可能拖过今年的秋天或是冬天。他提醒我说，他原来的计划是在六个月内采取行动。现在已经过去30个月了。”
在诺沃斯比尔斯克接触后，赫鲁晓夫与肯尼迪的首脑会晤好像将无限期推迟下去了，但是不到两个月后，他们却在维也纳会面了。与此同时发生的两件事情使得他们更加不可能在主要问题上取得一致意见了。尤里·加加林首次进行了太空旅行，美国支持下的反叛力量入侵古巴的猪湾以失败而告终，这使赫鲁晓夫增强了信心，认为可以用威逼的手段从肯尼迪那里获得他依靠甜言蜜语所没有得到的东西。
