尽管是在苏联的威逼下，但铁托还是邀请吉罗去了贝尔格莱德，并给以热忱的欢迎。不过，要想避免匈牙利发生骚乱已经太晚了，而且后来南斯拉夫人又变了卦。11月4日，他们让纳吉在南斯拉夫驻布达佩斯大使馆避难。（11月22日，在苏联承诺保证其安全的情况下，纳吉离开了南斯拉夫大使馆，但苏联人还是将他扣留了，囚禁在罗马尼亚，最后将他处决。）后来在11月11日的普拉镇讲话中，铁托努力把自己与苏联对匈牙利的干涉划清界限。[15]米库诺维奇来到克里姆林宫拜会赫鲁晓夫时还没有读到铁托的讲话，但赫鲁晓夫对他的态度极不友好，相比而言，先前7月份的冷淡都能算得上是热烈的拥抱了。没有一句问候的话，赫鲁晓夫将米库诺维奇拽进了一个空房间里，在那个房间里，他用了将近一个小时斥责这位南斯拉夫大使，当时莫洛托夫和布尔加宁就站在他的旁边。赫鲁晓夫最后意识到其他的客人可能会看到这种场面，于是他把米库诺维奇带到了另外一间较为隐秘的房间，又进行了一个小时的训斥。布尔加宁在旁边火上浇油，而莫洛托夫在大部分时间里则没有插话，脸上带着一种“我早就告诉过你”的表情。不过，赫鲁晓夫发过火后，却坚持开车送米库诺维奇大使和他的夫人（在整个过程中，她都一个人呆着）回大使馆。当赫鲁晓夫的汽车停在狭窄的赫勒比尼巷时，这位大使夫人下了车，但赫鲁晓夫还在车里对她的丈夫唠叨个没完。只是到了午夜过后很长时间，当时气温已经降到了10°左右，赫鲁晓夫才突然改变了口气：自从1954年以来，他就在改善与南斯拉夫的关系上倾注了大量的精力，甚至将此与他个人的威信联系在一起。现在他将不得不和他的同事们一起，公开抨击南斯拉夫，这使得莫斯科与贝尔格莱德之间的冲突进一步升级。“你要是看到我在南斯拉夫会谈与克里米亚度假后所写的书面报告，就知道我是多么希望改善我们之间的关系了。”他沮丧地说。
米库诺维奇在他的日记中写道，这“是我至今与赫鲁晓夫所进行的最为奇怪的交谈”。这位苏联领导人是个很好的演员，既能够故作生气，又能表面上装作友善，那天晚上他无疑将内心的伤痛宣泄到了极致。不过，这种伤痛是真实的，就像南斯拉夫人转而提到他所认为的对他个人的嘲笑时一样，当时他的气愤也是真实的。12月，米库诺维奇想去克里姆林宫进行一次短暂的交谈，结果又变成了一次马拉松式的三小时长谈。米库诺维奇发现：“赫鲁晓夫处于一种我从来没有见过的状态中，甚至在铁托的普拉讲话后，他也没有如此的激动。……赫鲁晓夫知道当他‘取笑南斯拉夫的玉米与土豆政策’时，（南斯拉夫副主席爱德华）卡德利（Kardelj）是如何评价他的。”两个月后，赫鲁晓夫仍然余怒未消。一周后，这位苏联领导人邀请米库诺维奇观看一场音乐会，就坐在他旁边，他低声对贝尔格莱德《政治报》上出现的关于他和布尔加宁的一幅“令人作呕的”漫画进行了强烈抗议，这位南斯拉夫大使指出，那个站在布尔加宁旁边的秃顶并不是赫鲁晓夫，而是艾森豪威尔。
赫鲁晓夫总是对细微的事情很敏感，当他的政策运行不畅时，他内心的不适感就与日俱增。唉，苏联与南斯拉夫的关系再也没有恢复到1956年夏天时的那种热络状态。当然，波兰和匈牙利还留在苏联阵营里，而不久南斯拉夫的光芒就开始在东西两方消退。不过，即使赫鲁晓夫赢得了胜利，也是付出了惨重代价的。铁托比以往任何时候都更加坚定地发扬南斯拉夫模式。赫鲁晓夫试图通过发起一场反对南斯拉夫“修正主义”的运动来限制他们的影响。在经过如此长时间热切地讨好南斯拉夫人后，他还是不得不采取这样的行动，这本身就是一种失败。[16]
中国和南斯拉夫能对苏联提出挑战，美国能摧毁苏联。即使不是更早，赫鲁晓夫到1954年时已经开始密切关注东西方关系了。他的儿子发现他在1954年1月的柏林外长会议期间“明显地紧张起来”。“他开始很晚回家，长时间与莫洛托夫进行电话交谈。”根据莫洛托夫一位助手的说法，赫鲁晓夫对这位苏联外长“反应迟钝、缺乏主动性”感到不满；他继续在同事们中间埋怨莫洛托夫的无能，经常是在外事招待会后有点“喝醉的情况下”。由于需要莫洛托夫的支持来反对马林科夫，因此在1955年初以前，赫鲁晓夫并没有直接与他发生冲突。与此同时，他开始主导防务政策，试图减轻防务给苏联经济所带来的负担，但是这并没有降低国家的战争准备，甚至反而提高了。他认为，解决问题的办法就是依赖核武器。
斯大林去世时，苏联开发原子武器的激进计划已经实施了八年时间。[17]美国情报机构1952年估计，苏联到1953年中可能拥有多达200枚原子弹。事实上，莫斯科到1953年中拥有的原子弹不超过120枚，到1956年，他们还没有能对美国进行长途奔袭后回到苏联本土的轰炸机。[18]然而，大量建造核武器会增加国防开支，而不是削减开支。赫鲁晓夫对这个两难问题的解决办法就是虚张声势。他的核心理论是，由于核武器的破坏性如此巨大，因此不可能用于实战；当第一次了解到“关于核力量的所有事情”时，他说：“我几天都不能入睡。然后我确信我们什么时候都不可能使用这些武器……这样，我才再次在睡觉时能合上眼睛。”这使他可以威胁发动核战争，但他的实际想法却是不会真正地冒此风险，同时削减像水面舰艇与轰炸机这样的常规武器。艾森豪威尔的“新视野”战略同样是威胁进行“大规模报复”，而不是对苏联的“侵略”进行常规反击。但是与苏联相比，美国有更多的核武器以及投射核武器的飞机。赫鲁晓夫选择了导弹来替代轰炸机。苏联最有可能的洲际弹道导弹是谢尔盖·科罗廖夫（Korolyov）研制的270吨的一级半“谢苗尔卡”导弹（R-7）。1956年冬天，该型导弹还有待进行飞行试验，但赫鲁晓夫已经开始在他与西方政治家的首次交锋中“利用”它了。
赫鲁晓夫新政策的中心就是发起一场后来被称为缓和的运动。按照他的观点，降低东西方间的紧张关系可以削弱西方对共产主义阵营的抵制，吸引资本家增加东西方贸易，并能在第三世界树立起共产主义阵营的良好形象。斯大林和莫洛托夫对“赢得喘息之机”的做法也表示欢迎，但赫鲁晓夫则倾向于能与资本主义世界永久地“和平共处”。他这么做并不是要放弃布尔什维克的革命使命，而是要在第三世界从事这种革命使命，他想在另一个领域内超过他的前人，因为斯大林和莫洛托夫对第三世界没有给予足够的重视。通过频繁的出国访问，利用个人的影响力让外国政治家时时关注他的国家与他本人，运用自身的精力与坚忍克服西方世界的不信任感，赫鲁晓夫想在对西方示好的同时削弱其影响。要是斯大林在世，他肯定会对赫鲁晓夫的做法大吃一惊。一位助手曾经听到莫洛托夫抱怨说，外交政策的幼稚病“是一种犯罪”。然而，这种蔑视只会激起赫鲁晓夫想取得成功的更大欲望。
克里姆林宫现在会为外交人员举行豪华宴会，宴会后接着是在圣乔治厅参加欢快的音乐会。在英国外交家塞西尔·帕罗特看来，1955年8月塞米扬诺夫斯卡娅的花园聚会创造了“一种令人着迷的气氛”，塞米扬诺夫斯卡娅位于莫斯科东南60英里处，他们在那里的几个小湖里泛舟，在高大树木间架起的吊床上小憩，在军乐队的演奏中享用着无尽的美味。赫鲁晓夫在浅色的热带外套下穿着他那标志性的乌克兰衬衣。在看到身材高大、奉行禁欲主义的苏斯洛夫“变成了一只白兔，从口袋里拿出几块手表，恨不得从钻进的地洞里消失”时，帕罗特肯定不会感到吃惊。这种情景让他想起了“莎士比亚笔下的奇境，布尔加宁在这种奇境里时而像普洛斯彼罗，时而又像阿尔丁森林里的爵士”。
然而，其他的聚会并没有收到他们想要的效果。1954年7月，******在赫鲁晓夫陪伴下出现在西方外交人士面前，这已经足以让海特尔大使改变他对苏联与中国“卫星国”之间力量对比，或者还有文化影响力之间对比的看法。******“说一口流畅、优美的英语，他的俄罗斯听众一个字也听不懂”，这让他的东道主感到很难堪。海特记得，在1956年6月图什诺（Tushino）航空展后的露天宴会上，赫鲁晓夫开怀畅饮，醉酒后“将世界上所有的国家逐个侮辱了一遍”。布尔加宁想打断他，莫洛托夫噘起了嘴，卡冈诺维奇低声嘀咕：“他说的那些话根本没有必要。”最后当赫鲁晓夫还在那里口若悬河时，他的几位同事就开始到处走动，互道再见了。
赫鲁晓夫关于东西方关系的第一个重要计划是奥地利。与德国一样，奥地利战后也被盟国所占领。赫鲁晓夫觉得，如果签订一项协议，根据协议，奥地利像瑞士一样能宣布中立，那苏联军队就撤出奥地利，这样对苏联也不失为一种不错的选择。与奥地利人的谈判已经中止了多年，一直从事这项谈判的莫洛托夫认为赫鲁晓夫是在干涉他分内的事。起初，赫鲁晓夫本人也不愿将自己的立场马上付诸实施。由于“在国际事务上缺乏经验”，他觉得自己就像“做好去欧洲准备的顿卡（Dun'ka）一样”，顿卡是康斯坦丁·特伦扬夫（Konstantin Trenyov）戏剧《流巴夫·雅罗瓦娅》里的一个头脑简单、没有文化的村妇，她的名字里就含有蔑视的意味。但是这种感觉并没有阻止他很长时间。
奥地利大臣朱利叶斯·拉伯是第一位赫鲁晓夫真正与之谈判的西方领导人。“你知道，拉伯先生，”他记得他当时说：“这是我有生以来第一次与一个真正的资本主义者坐在一起。”通过达成奥地利国家协议，该协议签署于1955年5月，赫鲁晓夫“通过了一场考验，证明我们能进行复杂的谈判，并能成功地达成协议”。他吹嘘说，最后“顿卡在欧洲表现不错；我们证明没有斯大林的指导，我们自己也能在外交事务中把握方向。事实上，我们已经将我们孩子时的开裆裤换成了成人的长裤。我们在国际舞台上的初次亮相不仅在苏联国内，而且也得到了国外的承认。……我们能感觉到自己的力量”。
赫鲁晓夫的下一场考验是1955年7月的日内瓦首脑会晤。20世纪50年代的首脑会晤还是四大国间的聚会，伦敦与巴黎急于想参与进来。但是在苏联人看来，美国才是主要的对手，美国也花了很大的气力想在这种外交斗争中取得成功。杜勒斯比他表现出来的更为灵活（对苏联集团里出现的分裂更为警觉，也更想降低冷战的紧张气氛），但是他认为一次首脑会晤是不可能取得什么成果的。然而，与赫鲁晓夫一样，艾森豪威尔喜欢采用“换位思考”的方法，对他所谓的对手“个人观察上的误差”进行揣摩，并通过自身个性的发挥来赢得彼此交锋中的主动。在首脑会晤前的那天晚上，杜勒斯私下里对一位朋友说，他感到“十分的担忧”。艾森豪威尔“喜欢直来直去，彼此能友好相处”，“当不愉快的心情无限期拖延时，就会厌倦”。杜勒斯担心艾森豪威尔会将对方策略上的微笑当做“内心热情的表示”，并根据“表面价值”接受对方的承诺。[19]
赫鲁晓夫与艾森豪威尔都认为应在达成实质性的协议前先建立私人间的联系，他们如此认为的一个理由就是实质性的协议当时还显得遥遥无期。德国问题以及与之相关的欧洲安全问题都没有什么妥协的空间：西方坚持通过自由选举实现德国的统一，苏联人却坚定地想让德国保持分裂状态。艾森豪威尔在日内瓦最激进的做法是提出了开放领空的建议，就是允许对彼此的军事设施进行观察飞行，这让赫鲁晓夫吃惊非小，认为这是将间谍活动合法化。[20]伯伦将日内瓦首脑会晤称为“所有首脑会晤中最令人失望与沮丧的一次”。海特说他在会晤的大部分时间里都在重读《战争与和平》，而阿纳托利·多布利宁（Anatoly Dobrynin），后来的苏联驻华盛顿大使，但当时只是一个低级外交人员，记得这样的“精彩场面”：当艾森豪威尔否认北约是“一个侵略性集团”时，赫鲁晓夫质问道，那他们为什么不允许苏联加入。“‘你们申请了吗？’艾森豪威尔吃惊地问道。‘就在几个月前。’赫鲁晓夫回答说。艾森豪威尔显然不知道该如何回答。”[21]