“艾森豪威尔和杜勒斯想干什么？”赫鲁晓夫在明斯克大发雷霆：“很显然，他们想会面，谈论在苏联取消社会主义制度的问题。……”好，希特勒已经尝试过了，结果以失败而告终，等待美国人的也将是同样的命运。[5]3月，赫鲁晓夫公开试探美国人的态度：“对于我们来说，莫斯科和华盛顿之间的距离并不是什么十分严重的问题。我们可以在家里吃早餐，在飞机上吃午餐，在美国吃晚餐。”[6]
5月，赫鲁晓夫愠怒地表示西方国家的反应“慢如蜗牛爬行”。[7]接着发生的一些事件更是妨碍了首脑会晤的举行。纳吉被处决激起了西方的抗议示威，对此苏联以“自发的”反集会予以回击。[8]在七月的一场军事政变中，伊拉克亲西方的国王法赛尔二世被杀害，这促使华盛顿与伦敦发兵黎巴嫩和约旦，对此赫鲁晓夫威胁将以武力保卫“伊拉克革命”。根据谢尔盖·赫鲁晓夫的叙述，他父亲起初感到很紧张，但不久就感到得心应手了：“在斗争最激烈的时候，父亲的感觉就像如鱼得水。”赫鲁晓夫告诉埃及总统纳赛尔说，他在危机中间曾来到莫斯科：“局势十分危险，我认为具有最坚强神经的人将成为最终的胜利者。”赫鲁晓夫好像十分喜欢他所谓的“进展十分快速的游戏，在这种游戏中，所有的人都必须采取快速的行动，不能准确判断其他的参与者下一步将会做什么。这就好像在黑暗中下棋一样”。
然而，即使是在这种游戏当中，他还是努力寻找首脑会晤的机会。1958年7月19日，他提议立即举行四大国加上印度的首脑会晤。对于英国的反对意见，他同意在联合国安理会的框架内进行会晤，当时他憎恨的蒋介石仍然占据着中国常任理事国的席位。将印度提升为一个大国，加上牺牲毛泽东，使国民党中国的地位合法化，这些都是非同寻常的过失。对于赫鲁晓夫来说，幸运的是，美国回绝了他的这一整套想法。不过，这一插曲还是让赫鲁晓夫感觉不舒服，8月阿德赖·斯蒂文森在采访赫鲁晓夫时明显地看出了这一点。当斯蒂文森无意当中提到安理会框架内的首脑会晤时，刚从中国回来的赫鲁晓夫厉声说：“我们不想和蒋介石坐在同一张谈判桌前。……没有人能让我们和蒋介石坐到一起。我们不喜欢这种氛围。”
1958年秋天的台湾海峡危机进一步拖延了东西方之间的会谈。赫鲁晓夫首先警告说，苏联会将任何对中国的攻击看作对自身的攻击，然后当危机几乎平息下去时，他给艾森豪威尔总统发去了一封辱骂性的信件，对此艾森豪威尔总统表示无法接受。但是，这位苏联领导人仍然坚决地想促成首脑会晤，他于10月8日告诉米库诺维奇说，这部分是由于苏联“在未来的15-20年内有着特别的安全需求”，在此之后“就没有人能与苏联相抗衡了，即使他们有这种想法”，此外也因为“欧洲出现的任何缓和都会削弱美国在世界广大地区的控制体制，削弱美国的军事联盟及其军事基地，从而在美国国内造成政治问题”。[9]
两天前，埃里克·约翰斯顿在皮聪大与赫鲁晓夫一家共度了一个下午的时光，约翰斯顿是美国电影协会主席，在华盛顿拥有良好的关系网，曾作为罗斯福总统的信使拜会过斯大林。他在皮聪大的拜会本来可以持续更长的时间（赫鲁晓夫邀请他共进晚餐，在那里过夜，第二天去打野鸭），但是约翰斯顿得回到莫斯科去。当天下午，赫鲁晓夫几次提到了他希望会见艾森豪威尔：“你知道，我真的很喜欢此人。在日内瓦会议上，每次会谈后他都会带我到吧台，我们在那里共饮一杯。我希望他身体健康。我喜欢坐下来与他再谈谈。”
赫鲁晓夫关于柏林问题的最后通牒就是将艾森豪威尔拉到谈判桌前的一种方法。到1958年秋天，特罗亚诺夫斯基回忆说，与西方的关系没有取得任何“突破”，而且“形势甚至变得越来越恶劣”。西德“正被更深地拉入西方联盟之中；军备竞赛日益加剧，并开始扩展到了外层空间；裁军谈判没有取得任何成果，防务开支对经济的负担日益加重；东德像以前一样被孤立，处于压力之下；苏联周围遍布着美国的军事基地；亚洲与中东地区正在组建新的军事集团”。此外，中苏关系正酝酿着麻烦，特罗亚诺夫斯基记得“苏联国内日益清晰地出现了这样一种声音，即如果苏联必须在西方与中国之间选择其一的话，那中国应成为我们的倾向”。
在特罗亚诺夫斯基看来，西德拥有核武器的可能性是最后的致命一击。“如果克里姆林宫对西德拥有核武器没有采取有效反击措施的话，那很显然，赫鲁晓夫的威望将一落千丈。”特罗亚诺夫斯基还怀疑他的主子仍然想努力证明莫洛托夫和其他人是错误的，他才是苏联至高无上的权威。
除了不知道自己的最终目标究竟是什么，以及如何才能达成这些目标外，赫鲁晓夫还错误地估计了他可能遇到的障碍。虽然他担心82岁老谋深算的西德总理阿登纳可能会“破坏他的计划”，但他对他所谓的“那个老古董”还是估计不足。与东德相比，西德虽然经济发展形势良好，但由于西柏林处于乌尔布里希统治的腹地深处，能否得到北约国家的全力支持还不清楚，因此阿登纳还是感到很脆弱。他的目标是将西德融入西欧社会，但是这可能会使其失去统一全德国的机会。对赫鲁晓夫努力寻求西方国家承认东德合法地位的举措，阿登纳极力表示反对。这位西德总理的固执与坚持让艾森豪威尔（以及后来的肯尼迪）感到心烦意乱，但考虑到西德的重要性，华盛顿在多数情况下还是按照阿登纳的意图行事。
戴高乐担心西方国家从柏林撤退将意味着德国的中立化，并最终导致苏德同盟的建立。这位法国总统一如既往的最终目标是恢复法国的世界大国地位，为此他需要阿登纳的积极支持。戴高乐比他的其他任何西方国家同事对赫鲁晓夫有着更深的了解；他感觉到这位苏联领导人是在讹诈，会在武装冲突面前止步的。因此在危机发展过程中，戴高乐甚至比阿登纳表现得还要强硬。
赫鲁晓夫在西方阵营中的最佳希望就是英国。由于各种各样的原因，从麦克米伦首相[10]担心赫鲁晓夫也许是个自大狂，到英国国内普遍流行的看法，认为不管俄国与东德是否会真的控制通往西柏林的通道，由于保守党即将参加不久举行的英国大选，因此不值得以核武器相威胁，英国希望承认东德的合法地位，并就西柏林的通道问题协商新的解决方法。然而，伦敦不久就发现自己在西方阵营内处于孤立地位。[11]
正如艾森豪威尔所认为的那样，对赫鲁晓夫屈服会导致西德局势的不稳定，损害西方国家联盟，使美国受到孤立。不过，他几乎和赫鲁晓夫一样对这种国际僵局感到焦虑，也很想寻求突破。艾森豪威尔对核战争会带来的危险感到很恐慌，1956年1月在听了空军关于有可能发生核战争初级阶段的汇报后，艾森豪威尔在日记中形象地描述了他的这种担心。空军的汇报设想了两种情况：其一，美国对苏联的原子弹攻击没有得到任何事先的警报；其二，美国有一个月的准备时间。在第一种情况下，美国将遭受“全面的经济崩溃”，有大约65%的公民需要医疗援助，“总体来看，美国是无论如何没有机会重新恢复过来的”，而苏联遭受的损失会比这严重三倍。艾森豪威尔写道，这“太可怕”了，在第二种情况下，“我们遭受的损失与此相比并没有什么太大的区别”。减轻损失的唯一办法就是发起突然袭击，但这“有悖于我们的传统”，也是不可能的，除非国会秘密宣战，不过那“好像也是不可能的”。
现在回顾起来，空军的汇报极大地夸大了1956年时苏联发起核战争美国可能遭受的损失。正如赫鲁晓夫所希望的那样，苏联的核潜能可以对美国总统的神经进行很好的考验，即使在其成为现实的战争手段之前。对于杜勒斯而言，苏联外交政策就好像是一本公开发行的书籍，具体地说，就是斯大林的《列宁主义的问题》，杜勒斯的办公桌和床头都摆放着这本书。但是艾森豪威尔仍时刻有这样的担心，就是莫斯科也许会在任何意想不到的时候让他大吃一惊。当赫鲁晓夫于1957年击败他的对手时，杜勒斯“对此并没有感到高兴，因为赫鲁晓夫此人并不可靠，行为怪异”，而艾森豪威尔则希望这位苏联领导人“也许会做出友好的表示”。
到1958年初，艾森豪威尔的挫败感与日俱增。美国正在失去一场宣传战，最为严重的是，正在日益失去和平的机会。2月9日，他向杜勒斯坦陈说，他已经开始感到“绝望了”。他考虑邀请赫鲁晓夫来美国进行“实地考察”，但杜勒斯表示反对：“没有人会相信的，我们对这样的首脑会晤没有任何准备，而且这也是我们以前宣称不会举行的。”艾森豪威尔转而考虑邀请不担任政府职务的主席团委员；双方并不举行谈判；“让他们在美国到处转转”。但是杜勒斯认为，在没有得到司法部长与国务卿同意的情况下邀请“共产党人来美国”是违反法律的。总统后来又想出了一个主意，就是吸收一万名苏联留学生到美国的大学里来。这听起来像个“花招”，杜勒斯反对说。此外，“我们也不大可能安排这么多的学生”。艾森豪威尔只得表示同意，但他仍“在寻求任何可以突破僵局的办法”。
对于赫鲁晓夫而言，他前进道路上最后的障碍就是他的东德盟友。乌尔布里希和阿登纳一样脾气古怪。他当然想得到西方国家的承认，但是他首先想得到的是柏林。对他来说，西柏林是他必须努力争取的战利品，而对于赫鲁晓夫而言，西柏林则是其打破国际僵局的控制杆。乌尔布里希要求的不仅是行动，而且还有苏联不断增强的援助力量。赫鲁晓夫愿意提供帮助。事实上，莫斯科一直在提供帮助，但是苏联经济本身也是压力重重。当柏林危机开始时，东德通过两个德国之间特殊的贸易安排享受特别的贸易通道，其产品可以进入西方市场。如果赫鲁晓夫继续实施他的威胁计划的话，失去这一贸易通道是不可避免的，这种损失不仅会损害到乌尔布里希的政权，而且也会使赫鲁晓夫的政权受到削弱，更不用说由此带来的不断增长的军事开支了——就在此时，赫鲁晓夫正努力削减苏联的军队规模与水平——如果危机继续持续下去的话。
如果西方国家坚持他们的立场，使得赫鲁晓夫与乌尔布里希单独签署协议，那他就不可能得到西方国家对东德合法地位的承认。如果他转而控制柏林通往东德的通道，那乌尔布里希就能下定决心，是想进行战争，还是要和平。由于西方国家领导人不能确定赫鲁晓夫是否是在讹诈，因此他们开始调动部队，准备强行进入柏林，以验证他们对赫鲁晓夫意图的判断。即使爆发战争，或者东德就像1953年时那样爆发起义，赫鲁晓夫也推断可以避免战争。但是，如果战争避免不了，那又会怎么样呢？出于种种考虑，他的总体战略（如果他的想法真能称得上是战略的话）从一开始就是怪异的。[12]不过，在一年多的时间里，他的战略还确实起到了作用。
对于赫鲁晓夫柏林问题的最后通牒，西方国家最初的反应是谨慎的。英国和法国都不准备支持哪怕是有限的武力使用，特别是在做出善意的谈判努力之前。艾森豪威尔和杜勒斯准备将东德边界的控制部队看做苏联的代理人，但是在西德的反对下，他们退却了。武装部队何时何地运用的问题需要在盟国间进行广泛的磋商。此时，就像艾森豪威尔在12月11日所说的那样：“我们的主要任务应该是与赫鲁晓夫取得联系，弄清楚他的真实想法究竟是什么。……”
1958年12月1日，国会参议员休伯特·H.汉弗莱与赫鲁晓夫进行了一次非同寻常的持续八小时的会谈，努力想刺探赫鲁晓夫的真实想法。根据特罗亚诺夫斯基的叙述，赫鲁晓夫在会谈中也同样想弄清艾森豪威尔与杜勒斯的想法。[13]这两个情绪高涨的（不用说狂躁了）对话者简直让人难以想象。汉弗莱在第二天的口述记录中说，他们之间的会谈也许是冷战历史上最富生气的。汉弗莱提出了会见请求，他于下午三点钟吃惊地得知会谈将在一小时后开始。四点半，他认为应该结束了，但赫鲁晓夫坚持让他留下来。在克里姆林宫内总理的办公室，他们分坐在一张长长的桌子两边，只有特罗亚诺夫斯基在场，两人一直谈到了七点钟，赫鲁晓夫吩咐将晚餐送进来。晚餐过后，赫鲁晓夫将米高扬招呼过来，三人继续争吵，一直到晚上11点钟。