实际上，赫鲁晓夫无意于把事情拖延下去。和维也纳的一次次谈判不得不很快启动，因为在西德加入北约之前，没有达成协议的任何机会。“维亚切斯拉夫·米哈伊洛维奇，你认为可以和奥地利签订和平条约吗？”2月底到3月初，赫鲁晓夫问莫洛托夫，“和奥地利政府谈判签约怎么样？”根据赫鲁晓夫的记录，莫洛托夫对此极力抵制：“管管你自己的事吧。我是一个老政治家，我有多年处理这类问题的经验，你才刚刚走上这条道。二战时我就是外交部长了！我开过各种各样的会议，也指导过许多关系我国事务的谈判。既然你来了，不要污辱我，不要把你那些不正确的、对我国利益有害的观点强加给我。”
然后，赫鲁晓夫就给这位“老政治家”设下一个圈套。利用权力，他将此事提交主席团会议，就莫洛托夫反对邀请奥地利政府代表团访问莫斯科的问题进行投票表决。3月24日，邀请函发往维也纳。此次访问从4月11日持续到15日，为订立条约作好了准备。
这位第一书记等不及通过第一次考验，就再次对苏联现行外交政策发动了一次更为广泛的进攻。1955年3月12日，赫鲁晓夫的支持者在《真理报》发表文章，发出苏联有意要和贝尔格莱德改善关系的信号。文章提议，铁托元帅应该“忘记过去，和苏联达成一致，共同为争取和平和国际安全而努力”。这只不过是一场大规模公共关系战役的开始，虽然不针对外交部长本人，但却要清除他的观念。
赫鲁晓夫让苏联最著名的人物——格奥尔吉·朱可夫元帅加入了这场战役。二战结束前几个月，艾森豪威尔在西线，朱可夫在东线。1945年，朱可夫任白俄罗斯第一军区司令，指挥进军柏林的战役。几周后，作为苏联代表参加受降仪式。朱可夫以斯大林允许的那种最受欢迎的英雄凯旋仪式回国的。和斯大林肩并肩站在列宁墓上，朱可夫凝视着一队又一队的苏军士兵把纳粹军旗踩在脚下。一年后，朱可夫发现自己处于不利的政治地位，成为斯大林偏执狂的牺牲者，虽然幸运地活着，但却重新回到乌克兰南部熬德萨军区司令的位置上。“好像就在同时，”长期关注克里姆林宫局势的观察家哈里森·索尔兹伯里说道，“杜鲁门把艾森豪威尔打发到俄克拉荷马去负责国民自卫队的训练工作。”斯大林一死，朱可夫就重返莫斯科，作为布尔加宁的副手，出任国防部副部长。布尔加宁升任总理后，赫鲁晓夫提名朱可夫接替布尔加宁出任国防部长。不久他又进入苏共中央主席团。
为了给莫洛托夫施加压力，朱可夫被要求在五一国际劳动节发表一次讲话。元帅很受人们欢迎，是一位可靠的盟友。没有哪个苏联人会怀疑这位战争英雄对国家安全所担负的责任。赫鲁晓夫相信，他不得不借助朱可夫来与莫洛托夫展开斗争。苏联官方一直强调二战的重要性，称之为伟大的卫国战争。“苏联的对外政策”，朱可夫说道，“是从伟大领袖列宁那里发展而来的，即不论其社会制度或国家结构，许多国家可以和平共处，经济上相互竞争。”
莫洛托夫提前收到一份讲话副本，马上意识到这是在挑战其外交权威。讲话提及“国家可以和平共处……”，这意味着要彻底反对与西方对抗的理念。4月30日下午5点，还有一小时朱可夫就要发表讲话，莫洛托夫向其同事散发一封信，要求对和平共存的声明进行更正。莫洛托夫争辩道，朱可夫的讲话等于赞同“和平主义”思想。莫洛托夫想使苏联的国力得到加强，而不是国际关系的缓和，这是苏联外交政策的目标。
莫洛托夫的要求被苏共中央主席团否决。
一周后，赫鲁晓夫再次授意朱可夫发出信号：南斯拉夫将是，朱可夫用很大篇幅来赞扬铁托在反法西斯战争中立下的汗马功劳。在该栏目的末尾，克里姆林宫插入一段政治评论：“作为参加过反法西斯全民战争的战士，我们非常愿意表达这样的愿望，一些争执（在贝尔格莱德和莫斯科之间就出现了争执）也会很快被解决，我们两国之间将会再次确立友好关系。”
莫洛托夫试图阻止这篇文章的发表。他把铁托视为法西斯分子，也很讨厌那种称赞二战期间南斯拉夫游击战争的想法。“托洛茨基缔造了红军，”莫洛托夫争辩道，“但我们并不赞扬他。”
莫洛托夫的同事们再次否决了他的意见，文章一字未改全文发表。其中，阿纳斯塔斯·米高扬在反对外交部长的投票表决上对赫鲁晓夫的支持最大。除莫洛托夫外，主席团委员里最富有外交经验的是米高扬。1926年以来，他曾几次出任苏联外贸部长。1936年，米高扬还到美国研究其食品生产体制。品尝过美式冰激凌后，米高扬非常喜欢，回国后，苏联也开始生产这种食品。如果说赫鲁晓夫因为在玉米生产方面成绩突出而获得“玉米棒子同志”的称号，那么，米高扬也会得到“蛋卷冰激凌同志”的称号。然而，米高扬过去并非事事顺利。他曾参与过和纳粹德国的谈判，1939年苏德签订互不侵犯条约。次年，莫斯科和柏林同时入侵波兰，他和其他人一同签署了处决4万被俘波兰军官的命令。这些人被处死后埋在卡廷森林。米高扬的内心极为复杂，从不同意马林科夫否定战争不可避免的说法，赫鲁晓夫相信他在外交事务方面的判断。1954年秋，赫鲁晓夫曾邀请他一同访问中国。
1955年5月19日的主席团会议上，莫洛托夫称朱可夫是反列宁主义分子，米高扬和布尔加宁总理都有意立即表态支持朱可夫，以及和平共处的新政策。“你再不要这样指责他人，说‘反列宁主义分子’。”米高扬说。在苏联，这个词和约瑟夫·麦卡锡所称的“反美分子”一样带有污辱性。
“莫洛托夫就像一只上足了发条的玩具，”赫鲁晓夫事后回忆道，“一旦发条被松开，齿轮和轮子就会不停地转动，直到发条松弛为止。”尽管莫洛托夫确实承认，说朱可夫是“反列宁主义分子”只是一时冲动，但他绝不赞成赫鲁晓夫及其支持者所坚持的立场，也拒绝改变自己的立场。
然而，赫鲁晓夫利用投票表决启动了和南斯拉夫的高层会谈。贝尔格莱德主动回应苏联的提议，即5月派出高级代表团访问南斯拉夫。莫洛托夫还想阻挠这次访问，却并未达到目的。代表团访问南斯拉夫前夕，主席团安排两次特别会议。会上，莫洛托夫几乎反对代表团所做的一切准备工作。苏联的规则是，只有主席团才能取消对官方代表团的正式指示，而这些指示通常由外交部来准备。外交部也要草拟“最后”的谈判公报，苏联政府以后要把它推荐给参加谈判的伙伴国。尽管莫洛托夫主管外交部，但是主席团迫使外交部门在准备这些文件时不使用莫洛托夫式的语言风格。莫洛托夫非常鄙视他们。每次表决这些文件时，他都投反对票，每次投票结果都是八票支持，一票反对。
访问南斯拉夫，是赫鲁晓夫主导苏联外交政策后的首次出访。然而，南斯拉夫似乎并不明白莫斯科发生的这种变化，仿佛他们接待的是斯大林和莫洛托夫主管下的苏联外交代表团。5月26日在欢迎代表团抵达贝尔格莱德的仪式上，主人嫌麻烦，甚至没有翻译赫鲁晓夫的讲话。“这里每一个人都懂俄语。”铁托这样解释道。而赫鲁晓夫则怀疑这是借口。“我懂乌克兰语，但如果一个人说得快些，我还是听不懂。”赫鲁晓夫事后回忆道，“而乌克兰和俄罗斯的距离比俄罗斯和塞尔维亚-克罗地亚要近得多。”这位苏联第一书记的一个鲜明印象是，不是所有的外交礼仪都得到了遵守。
尽管有些怠慢，赫鲁晓夫还是兴致勃勃。尽管知道苏共主席团的三驾马车不系黑白两色领带，然而，赫鲁晓夫的南斯拉夫主人还是在贝尔格莱德郊外铁托的冬宫举行了一场白领带欢迎会。赫鲁晓夫身着深蓝色西服赴会，他走下汽车，许多照相机和闪光灯迎面而来。让南斯拉夫人和聚集在一起的外国记者吃惊的是，他们离现场很近，甚至一伸手就能触摸到赫鲁晓夫。这位初出茅庐的苏联领导人对此友好地回应着。“他站在那儿，”《伦敦每日电讯报》驻莫斯科记者爱德华·克兰克肖回忆道，“还让记者拍照，面带微笑。”对外界来说，赫鲁晓夫似乎在对自己说：“到底发生了什么？显然这是我不得不忍耐的。我会容忍它。”他从容应对，就像任何一位“从小就习惯这些的西方政治家”。
然而，赫鲁晓夫还面临着访问的压力。正式晚宴临近结束，他喝多了。带着一股酒劲，他向记者们喊道：“你们为什么不到我国参观？”有些记者抱怨道，他们很想去，但申请不到签证。赫鲁晓夫挥舞着手臂，许诺发给他们签证。酒精起作用了，最后，赫鲁晓夫不得不让人扶下楼梯，坐车回到苏联大使馆。几个小时前，米高扬想带他离开，这位苏联领导人不走。“不，”赫鲁晓夫说，“你以为我醉了？我没有醉。你是美国人，你喝不了这么多酒，但我感觉很好。我感觉很好。”
在南斯拉夫就像在家一样。外出参加正式活动时，赫鲁晓夫却又精神十足地为社会主义而战。在那里，他表现出的生气、活力和精神吸引了许多的观察者，不管他们有何种文化背景。参观一家工厂时，其个性暴露无遗。在工厂一楼，赫鲁晓夫、米高扬、布尔加宁，还有工厂经理和两个记者，挤进工厂经理狭小的办公室。经理解释了工人委员会人员组成情况。当赫鲁晓夫讲话时，仿佛马上变成了工厂负责人，滔滔不绝，大谈水泥的特点、用处。讲话时间很长，却从未被米高扬和布尔加宁打断过。当布尔加宁想让报道这次访问的一位漂亮女记者出洋相时，赫鲁晓夫很快狠狠地扫了他一眼，布尔加宁停住了，一下子变得面无表情。“我第一次意识到，”现场的另一位记者克兰克肖回忆道，“这是一个内力强大的人，显然，在国内他能毫无困难地支配其所有的同事。”
一俟从贝尔格莱德回来，赫鲁晓夫而不是布尔加宁，就在6月6日向主席团提交正式出访报告。赫鲁晓夫承认，和铁托的高层会谈并未完全达到预期目的。在经济和国与国事务方面，苏联代表团达成一些协议，但在苏共和南共两党关系等敏感问题上，仍存在分歧。
离开贝尔格莱德之前，莫洛托夫要代表团找出答案，铁托领导的是一个资本主义国家还是无产阶级国家？其用意是，这个问题的答案是指导未来两国关系的前提。对莫洛托夫而言，如果把南斯拉夫定义为一个无产阶级国家，就不得不把国际共产主义的领导者——苏联的利益放在前面，而不是它自己狭隘的地方利益。
赫鲁晓夫和代表团对莫洛托夫的问题给出了非常微妙的答复。在赫鲁晓夫的要求下，《真理报》的编辑德米特里·谢皮洛夫也成为代表团成员。他的回答是，南斯拉夫“不是一个资本主义国家，而是一个人民共和国”，不过它还不是一个与莫斯科保持一致的人民共和国。在苏联代表团和铁托及其宣传部长的多次会谈中，南斯拉夫拒绝对他们的解释作出让步。对莫洛托夫来说，这正好是放弃与贝尔格莱德保持密切关系的借口；而对赫鲁晓夫、米高扬和布尔加宁，还有赫鲁晓夫的支持者拉扎尔·卡冈诺维奇来说，这是可以接受的。现在最需要一种新学说来代替斯大林-莫洛托夫的老一套外交政策。“要有信心，”两天后赫鲁晓夫对同事说道，“我们还要努力，必须逐步强化我们的立场，要把南斯拉夫拉到我们一边。我们一定要树立信心，不要有失败主义情绪。”
赫鲁晓夫和莫洛托夫的意识形态之争已经远远超出克里姆林宫与铁托的关系问题。如果主席团顺从赫鲁晓夫的领导，放弃那种迫使潜在伙伴陷入意识形态怪圈的传统，那么苏联潜在伙伴的数量将会增长三倍多。尤其这是一个正在变化发展的世界，这种改变将会有更大的收获。与此同时，南斯拉夫之行已经在警告莫洛托夫，无论其立场如何，现在他已经在未来苏联外交政策之争中处于守势。
从贝尔格莱德回来后一周，在苏共中央委员会的一次秘密全会上，赫鲁晓夫肯定了此次访问。这个会议两年召开一次，有300名左右的中央委员参加。他和布尔加宁谈及莫洛托夫对朱可夫毫无根据的指责，以及他对南斯拉夫所持的不妥协立场。
苏联媒体并未披露对莫洛托夫的讽刺和批评。因此，无论英国还是美国记者都没有得到什么重要的消息，媒体也无法接近克里姆林宫，不知道赫鲁晓夫和莫洛托夫之间的斗争，以及内斗对国际安全的影响。然而，赫鲁晓夫下一步要采取的外交政策极为重要，伦敦和华盛顿都不会错过。
