8月26日，《纽约时报》记者赛勒斯·苏兹贝格意外收到一封电报，其时他正住在希腊斯派采伯罗奔尼撒小岛上的一家旅馆里。尤里·朱可夫是苏联一个地位很高、非常迷人的宣传员，朝鲜战争爆发以来，他一直是克里姆林宫著名的新闻发言人。电报称他要向老朋友提供有趣的新闻。如果记者能自己到莫斯科，赫鲁晓夫可能会会见他。朱可夫建议苏兹贝格9月2日或3日到莫斯科，那时苏联领导人将会从黑海度假胜地回来。朱可夫没有泄露赫鲁晓夫要谈哪些内容，但是，在1961年8月，人们谈论最多的还是柏林问题。
几天后，苏联驻南斯拉夫大使通知其美国同事乔治·凯南，称尼基塔·赫鲁晓夫“热情地支持”在两国大使间就柏林问题“展开进一步交流”。华盛顿已经准备利用凯南来向克里姆林宫传达美国的外交兴趣。筑起柏林墙的次日，美国国务院已经授权凯南接近苏联驻南斯拉夫大使，向他试探和赫鲁晓夫进行联系的机会。8月14日，克里姆林宫还未做好准备，现在准备就绪。
与此同时，苏联驻比利时使馆代办向比利时外交部长发出访问莫斯科、会见赫鲁晓夫的邀请。保罗·亨利·斯帕克个子不高，来自一个小国，然而，他却是欧洲一个令人尊敬的人物。1961年2月以前，他一直担任北约秘书长，之后回到布鲁塞尔任外交部长。7月底，斯帕克曾委婉地向莫斯科传递出他的想法：可通过谈判来解决问题。直到现在，莫斯科才开始采纳其建议。
一个知名的小个子法国人也收到他的第四次邀请。1961年夏末，83岁的法国前总理保罗·雷诺将访问苏联，出席在莫斯科举办的法国商品和技术展览会闭幕式。克里姆林宫安排赫鲁晓夫会见雷诺，并不在其计划之中，会见更多具有象征意义。1940年5月，希特勒入侵法国，绝望之中辞职的正是雷诺。这个在法国历史上有名无实的人物将会被要求在1961年帮助苏联劝降西方。
为尽快启动谈判，在皮聪达赫鲁晓夫就已决定要试探一下西方。之所以接近苏兹贝格和凯南，就是要和肯尼迪建立一个新的秘密联系渠道。赫鲁晓夫正在探索肯尼迪谈判立场上的一些变化。赫鲁晓夫还想得到斯帕克和雷诺的理解和支持。确定柏林策略时，他曾期待西欧向美国施加更大的压力，让其接受苏联的条件，从而避免战争。现在赫鲁晓夫依然相信，可以利用西欧来分化美国的决心。因此，他决定讨好这些有劝和兴趣的欧洲知名人士。
当苏联驻外人员把这种外交攻势付诸实施时，赫鲁晓夫自己就感受到了这种令人吃惊的倡议的效果。如果那个夏天收到赫鲁晓夫的私人信件，对凯南、雷诺、斯帕克和苏兹贝格来说是最出乎意料的事，那么，阿登纳秘密接触赫鲁晓夫，则更让人震惊。1961年8月29日，西德总理向其俄国同行发出密信。信是西德大使科尔递交的，苏联外交部翻译如下：
总理想让其对手知道，他完全同意赫鲁晓夫的看法，即要适当对待日益加剧的局势，而不是一味感情用事。联邦德国知道，无论艾森豪威尔（原文如此）还是赫鲁晓夫，都不想发动战争。但是，可能会爆发一场战争。现在面临着两大危险：当双方坦克面对面时，相距仅数米远，就像现在的柏林，而更大的危险则是对局势的错误判断。联邦德国深信，谈判是缓和当前局势的唯一出路，必须尽快启动谈判。联邦德国的谈判立场和美国、英国的立场完全一致。众所周知，对于谈判开始的时间，法国有其特殊考虑。
西德领导人公开表态称，和莫斯科谈判是危险的，因为他们可能会导致西方在柏林问题上作出让步。然而，通过科尔，阿登纳向克里姆林宫强调，苏联没有理由要等到9月17日西德大选之后再开始谈判。而且，西德还要求莫斯科释放仍被扣押在苏联的最后一批德国战俘，以此来显示其缓和紧张局势的诚意。赫鲁晓夫一向认为，他最终能把波恩从华盛顿那里吸引过来，阿登纳的倡议对他的这个固执想法产生了作用。或许这只是诡计多端的阿登纳在大选前玩弄的一个花招，但是，在即将开始的谈判中，只要他能得到，赫鲁晓夫需要所有来自欧洲的帮助。
9月5日，赫鲁晓夫和赛勒斯·苏兹贝格谈了5个小时。他给这位记者足够多的素材，足可以发表系列头条新闻。然后，他把话题转到为何要展开谈判的原因。赫鲁晓夫交给苏兹贝格一页纸，在肯尼迪看来，那是一张个人便笺。赫鲁晓夫建议，两国领导人建立“某种形式的非正式接触……以找到解决危机的办法，而又不损害美国的声誉”。他只要求肯尼迪“原则上同意这项和平条约和建立一个自由城市”，没有要求肯尼迪接受失去进出西柏林的权利，这还是第一次。
这与肯尼迪不谋而合。肯尼迪也在苦苦思索如何以谈判方式来解决危机。1961年9月，肯尼迪要作出一些颇不令人愉快的决定。如果他想明年初在欧洲部署6个多师，那么，宣布全国进入紧急状态就不能拖得太久。军方，还有一些非军方的助手都仍然认为，他只是推迟了7月的决定而已。但是，肯尼迪感到疑惑的是，是否真的需要部署这6个师。美国是否要继续进行核试验也要作出决定，这也是他面临的压力。一个来自更大范围的建议是，鉴于苏联已在塞米巴拉金斯克进行系列核试验，美国实际上已别无选择。
甚至在赫鲁晓夫会见苏兹贝格之前，肯尼迪就对苏联接近乔治·凯南的新闻予以积极回应。克里姆林宫似乎准备谈判而不是大吵大闹，尽管肯尼迪需要比凯南和苏联大使更高级别的会谈。苏联外交部长葛罗米柯也准备9月底来纽约出席联合国大会开幕式。9月3日，美国国务院指示汤普森向苏联人建议，举行腊斯克和葛罗米柯的会谈。其时汤普森不在莫斯科，要让赫鲁晓夫知道肯尼迪对会谈感兴趣，那要花上好几天的时间。
在华盛顿，肯尼迪向其顾问发出一个强烈信号，他想让这些会谈真正取得成功。9月12日，他命令国务卿腊斯克召集小范围的顾问会议，为美国政府在结束柏林危机的谈判中应坚持的立场做好准备。肯尼迪把这项任务分配给国务院，那是他绝望的一个标志。危机爆发以来，肯尼迪开始把美国外交官群体形容为“一团糨糊”。他怀疑，在缺乏坚强领导的情况下，美国能不能向赫鲁晓夫提出某种新思维。“我在说要重新提出一套我们的谈判建议，“他敦促腊斯克，“而不是适当增加某些内容。”美国对赫鲁晓夫6月通牒的正式回应是腊斯克和法国人、英国人、西德人共同起草的，它有些枯燥乏味。肯尼迪非常清楚，在和苏联人的任何谈判中，主张在自由选举的前提下实现德国或柏林的统一是不切实际的想法。“这些都不是可以谈判的方案，”他提醒腊斯克，“他们在这个方面的无知众所周知。”
肯尼迪决定把重新思考美国立场的任务限定在小范围内。迪安·艾奇逊和林登·约翰逊已确定不参加谈判，将被排除在外，而且肯尼迪也不想让五角大楼的任何人知道他所做的这一切。在白宫，只有总统国家安全事务助理麦乔治·邦迪和总统撰稿人索伦森知道这件事。总统确实给他们提供了进行创造性思维的空间。肯尼迪准备考虑把西柏林变成一座自由城市。但是，他想让北约能为这座城市和其居民提供保护，而不受苏联或东德的干涉。
肯尼迪对阿登纳接近赫鲁晓夫一事一无所知，他还在期待这位西德领导人成为一个最坚定的盟友，要他相信需要提出新的方案，尤其是那种暗示西柏林不可能成为西德一部分的方案。一旦准备好新的谈判方案，肯尼迪就打算派阿登纳尊重的人士，甚至可能是艾奇逊，去向他兜售这套方案，当然，如果肯尼迪能首先把这套方案兜售给他自己的那些强硬派的话。
9月中旬，正当赫鲁晓夫要会见两位特别挑选的欧洲人士时，他得到消息，肯尼迪想让腊斯克和葛罗米柯在纽约举行会谈。美国大使没有提及美国的任何新立场，但是，赫鲁晓夫受到鼓舞，至少肯尼迪似乎准备就他提出的柏林要求进行谈判。他同意苏联参加会谈，时间定于9月21日。
与此同时，德国发生的事件也在提醒人们所面临的风险：双方都在允许这种危机持续下去。9月14日，中欧时间下午5点刚过，两名西德飞行员驾驶的F-84“雷电”战斗机越界进入东德领空——马格德堡西南76公里处空域。苏联空军仍在执行那道要击落任何进入东德领空飞机的命令。然而，8名苏联飞行员未能发现并拦截住这架西德F-84战斗机。21分钟后，两架西德战机降落在西柏林法国占领区的泰格尔机场。次日，西德另外两架F-84战机再次侵犯东德领空。这次仅持续4分钟，对苏联空军来说算不上失败，然而，这种行为仍然不受欢迎，它也说明东德主权容易遭到侵犯。两次意外事件让驻德苏军司令部深感忧虑，而且也引起赫鲁晓夫的疑问，即尽管阿登纳在两周前就发来密信，但西德人可能还准备挑起一场冲突。
当赫鲁晓夫正在分析两次意外事件的用意时，沃尔特·李普曼发表于《纽约先驱论坛报》的一篇文章被及时译成俄文，并送到他的案头。文章标题为“核外交”，它是美国权威专家对国际政治所做的敏锐观察，即在这个世界上，没有哪一个超级大国有能力来摧毁另一个超级大国。“我们不能理解赫鲁晓夫—肯尼迪对抗的现实，”李普曼写道，“除非我们提醒自己，核战争并不是另一场历史上描述的那种战争，而是一种全新的暴力法则。”赫鲁晓夫同意这一观点，迫使西方接受西柏林新的现状毕竟是他提出冒险策略的基础。这位苏联领导人认为，在一个核武器支配的世界里，理性的男人应该害怕战争，从而选择外交方式，甚至投降的方式。
9月16日，当着保罗·雷诺的面，赫鲁晓夫称赞李普曼及其专栏文章：“这是一个明白事理的人，我同意他的许多观点。他肯定了今天的战争就是自杀。”但是，赫鲁晓夫显然不理解或者不愿讨论李普曼文章的结论，“因为这是核时代。”李普曼的结论是，“国际政治的最高原则是，一个核大国一定不能把另一个核大国置于必须要在自杀和投降中作出抉择的境地。”
本来希望核恐惧将会让两位欧洲贵宾变得更为顺从，但这个希望很快就破灭了。赫鲁晓夫和雷诺三个小时的会谈不过是一场滑稽戏。这个法国人原来是个不会认错的白人帝国主义分子，他对黄祸的忧虑甚于核威胁。“前两次欧洲战争把世界霸权地位拱手让给了美国人，”这位前总理主张，赫鲁晓夫没有义务来停止其武力恫吓，“一场新的战争将会导致白种人的自杀，而给中国统治世界创造机会。”这些看法对赫鲁晓夫来说毫无价值，但他还是告诉雷诺，作为一个国际主义者，他把阶级置于种族之上。这位苏联领导人和毛泽东确实有麻烦，但是他不打算以种族的标准和这个法国资产阶级的代表来谈论其中国盟友。
几天后和斯帕克的会谈少了一些疏远，但也不成功。这个比利时人的说法引起克里姆林宫的兴趣，“就像苏联所宣布的那样，让西柏林变成一座自由城市并保证一定的进出自由权利，这个方案可以让西欧国家和他（赫鲁晓夫）达成一个协议”。这样，在和一个苏联东欧集团外交家的会谈中，斯帕克就成为支持西柏林自由化概念的第一个西欧外交政策的制定者。然而，一旦这个比利时人从其职责出发，而且两个人讨论起具体问题时，那么，赫鲁晓夫的种种希望很快就会破灭。斯帕克依然支持西柏林自由化，但也希望北约保留其进入这个城市的特殊通道。赫鲁晓夫结束和雷诺、斯帕克的会见时还在想，他还没有见到一个接受其西柏林自由理念的西欧人物。
如果赫鲁晓夫认为现在他给予欧洲的比他从欧洲得到的更多，那么，他可以被原谅。和雷诺和斯帕克的会谈中，赫鲁晓夫披露，他准备看着联合国将其总部迁移到西柏林。这戏剧性地描绘出他的愿望，即让西柏林未来继续保持独立地位，甚至保留其资本主义制度。艾森豪威尔确实曾经玩笑似的提到，建议把联合国总部迁至西柏林，可是约翰·福斯特·杜勒斯却制止了这个想法。在和斯帕克的会谈中，赫鲁晓夫也曾无意中透露，他对启动谈判并没有设置最后期限，那意味着他或许愿意解除1961年那个即将到期的最后通牒，就像他在1959年所做的那样。斯帕克谈及9月底北约理事会将召开特别会议时，赫鲁晓夫并不显得特别着急。他说，这位苏联领导人“宁愿选择迟到的谈判而不愿选择匆忙发动的战争”。
9月21日，一次漫长的午餐后，腊斯克和葛罗米柯在纽约开始会谈。两个人都没有什么新鲜内容要说。赫鲁晓夫设想，球在肯尼迪一边，而且对美国政府柏林策略的考察还要几周时间才能结束。肯尼迪是在9月12日启动其柏林策略的。
然而，赫鲁晓夫对两国外长的首次会谈却非常满意。他赞许道，腊斯克没有对柏林墙提出任何批评。葛罗米柯后来向中央委员会证实，“美国代表在会谈中承认，1961年8月13日的措施符合民主德国和其他社会主义国家的核心利益”。赫鲁晓夫大概也很喜欢肯尼迪政府抛弃艾森豪威尔政府的做法，即仅仅就包括东、西柏林在内的大柏林地区成为一座自由城市进行谈判。尽管各方对柏林问题的看法依然不同，但至少美国人现在愿意就西柏林问题展开讨论，仿佛这是一个单独的实体。