如果米高扬听出了毛泽东的弦外之音，那赫鲁晓夫对此会怎么看呢？“列宁曾经说过，世界上没有人一生不犯错误，”毛泽东宣称：“我就犯过很多错误，这些错误对我来说是好事，让我吸取了教训。……中国有句俗话说，红花虽好，还需绿叶的陪衬。你，赫鲁晓夫同志，尽管是朵红花，但需要绿叶的陪衬。我，毛泽东，尽管还算不上一朵红花，但也需要绿叶的陪衬。中国还有句古语说，三个臭皮匠顶上个诸葛亮。这与赫鲁晓夫同志的口号——集体领导——是一致的。”
这是否称得上是一种赞誉？还有，如何理解毛泽东关于战争的看法？“如果形势进一步恶化（爆发核战争），人类的一半将在战争中被毁灭。”毛泽东在11月会议上说：“那还有一半会幸存下来，而帝国主义世界将会被夷为平地，到那时，世界将是社会主义的。”如果西方侵略苏联，他劝告赫鲁晓夫说，苏联军队不应该反击，而是应该在三年内撤退到乌拉尔去，到那时中国会解救他们。“我仔细地看着他，”赫鲁晓夫后来说：“我从他的脸上看不出他是否在开玩笑。”
毛泽东在莫斯科的个人行为传达了一种更为明确的信息。与斯大林明显不同的是，赫鲁晓夫对毛泽东倾注了极大的关注与热情。他把客人安置在曾经属于凯瑟琳大帝的富丽堂皇的宫殿里，为他提供了数不清的水果、巧克力、香烟与饮料，每天早上都去看望他，并亲自陪伴他去参加政治集会与文化活动。他简直不能再“友好和尊重”了，毛泽东的医生回忆说。然而，毛泽东实际上对此还是流露了不满与无礼的。凯瑟琳皇宫卧室里的巨大软床让毛泽东觉得不舒服，于是他就睡在地板的毯子与床单上。他也不喜欢隔壁卧室里的豪华卫生间，他使用自己的夜壶。虽然苏联人为他准备了两位俄国厨师，但他只吃他的私人厨师做的湖南菜。去大剧院看《天鹅湖》时，他拒绝坐在赫鲁晓夫的包厢里，而是坚持与“大众”坐在一起（其实那里根本没有什么大众，特别是前三排通常都是由克格勃的人占据着，他们把普通观众都清理出去了，好让毛泽东能好好欣赏管弦乐队的演出），后来他又要求马上离开。李医生说：“他好像是故意拒绝欣赏俄罗斯文化。”在与中国同事的私下交谈中（克格勃肯定监听并汇报了这些谈话），毛泽东在谈到他的东道主时满嘴“带刺”。赫鲁晓夫想努力弥补斯大林1949年对毛泽东的失礼，但结果却招来毛泽东的攻击。“看看他们现在对我们的态度差别多大，”毛泽东不屑地说：“甚至在这块共产党人的土地上，他们也知道谁是强者，谁是弱者。这些势利小人！”
毛泽东的话传到了双方的低层官员那里。他把赫鲁晓夫看成是个“喜欢阿谀奉承的笨拙的傻瓜”，列夫·德柳辛回忆说。在李跃人（音）的记忆里，赫鲁晓夫并不了解毛泽东。“他不了解毛泽东是个伟大的领袖，跟他说话要深思熟虑。”
赫鲁晓夫1955年5月的贝尔格莱德之行比他的北京之行风险更大。他处理苏联集团事务的新模式是容忍少量的多样性与国内自治，强调意识形态与政治联系，增强经济与军事联系，并通过他本人的直接参与将这一切都交织在一起。但东欧的斯大林主义者对他的方案进行了抵制，他表现出来的自负也同样遭到了他们的抵制。虽然赫鲁晓夫承认斯大林对东欧国家的剥削，但当他们不承认苏联共产党的“领导地位”时，他马上表现出了愤怒：“尽管我们在处理与其他社会主义国家的关系时出现磕磕绊绊……但我们从来没有利用这种友谊来为任何自私的目的服务。”然而，正是他的这种态度，自以为是而又有失偏颇，促使问题产生了，同时还有他的那种俄罗斯优越感。波兰人忘恩负义，他们对苏联的援助并不领情，总是要求更多的帮助。赫鲁晓夫在他生命的最后阶段说，所有的社会主义国家“都把苏联看成一个巨大的赈济所。我知道这一点，因为我与他们都打过交道”。加上他采取了粗鲁的恃强凌弱策略，这些策略在其他国家共产党领导人看来再明白不过了，因为他们相互之间以及对自己的民众都采取了这些策略，我们可以清楚地了解为什么在更为自愿的基础上重建苏联共产主义阵营是如此的困难了。
当斯大林式的清洗于40年代末传播到东欧国家时，对于像匈牙利的拉斯日洛·拉吉克（Laszlo Rajk）与捷克斯洛伐克的鲁道夫·斯兰斯基（Rudolf Slansky）之类的“叛徒”最恶毒的称谓就是他们是铁托主义的间谍。西方国家抓住苏联与南斯拉夫分裂的时机与铁托建立经济，甚至是军事联系。如果南斯拉夫现在能重新融入“社会主义大家庭”，那未来也许是光明的。1955年5月去贝尔格莱德是需要勇气的，赫鲁晓夫的南斯拉夫之行好像也取得了成功。苏联和南斯拉夫领导人郑重发誓“在处理双边关系以及与其他国家关系时，尊重国家的主权、独立、完整与平等权利”。铁托后来告诉他的同事们：“只有赫鲁晓夫能做到这些。莫洛托夫、马林科夫、伏罗希洛夫——他们谁也不能改变任何事情。”
但是这第一次的沟通就建立起了一种模式，这种模式后来使赫鲁晓夫深受其害。铁托急于达成两国的和解，但是根据他自己的想法。他的目的是改变社会主义阵营，而不是无条件地支持。他想保持南斯拉夫的独立性，包括在与西方的关系上，而不是使其受到限制。由于在赫鲁晓夫之前已经与斯大林闹翻，铁托的性格孤傲而倔强。赫鲁晓夫需要南斯拉夫作出意义深远的让步，以证明他与铁托和解是正确的，而铁托则坚决拖延两党间建立亲密的关系，直到斯大林主义在苏联消亡。
当赫鲁晓夫到达南斯拉夫时，贝尔格莱德机场就显示出了双方的紧张关系。铁托表达了礼貌的欢迎后，赫鲁晓夫走到麦克风前。他的讲话稿经过了主席团的仔细起草与审查，将过去对贝尔格莱德的过失归咎于贝利亚，而不是斯大林。赫鲁晓夫结束讲话后，铁托打断了翻译。“没有必要翻译了，这里所有的人都懂俄语。”他说。然后大步走开，将苏联客人引上了等候的汽车。赫鲁晓夫后来喜欢引用贝尔格莱德机场上发生的情况来说明不能仅仅通过指责贝利亚来替斯大林开脱罪责。不过，当时他还是感到十分的懊恼。因为绝非所有的南斯拉夫人都懂得俄语，铁托实际上是在责骂他的苏联客人。那些留在莫斯科、反对这次访问的人“是很有势力的”，赫鲁晓夫后来说：“在贝尔格莱德受到的冷遇可以看作一种敌意的行为，让我们感到受到了挫伤。”
经过贝尔格莱德机场的冷遇后，尴尬接踵而来。铁托和他的高级部长们穿着礼服来到了豪华的招待会上，他们的夫人也是盛装出席，而赫鲁晓夫一行人却穿着皱皱巴巴的夏装。在苏联代表团在南斯拉夫国内考察期间，接待规格很显然受到了严格限制。铁托带着赫鲁晓夫乘坐一艘马力强劲的摩托艇在亚得里亚海上兜风，把他颠得差点都散了架。赫鲁晓夫在苏联大使馆的招待会上醉得不省人事。在后来与铁托及其夫人聚宴时，米高扬一个接着一个地唱赞歌，布尔加宁努力让主客间的交谈保持顺畅，赫鲁晓夫则不停地亲吻所有的人，特别是铁托，他不停地对铁托说着贴心的话：“伊奥斯亚（Iosya），不要生气了！你瞧你现在多瘦啊！喝酒，过去的事情就让它过去吧。”
赫鲁晓夫在不需要外交手腕的场合表现得更好一些。在萨格勒布的一个工厂里，他坐在一张圆桌旁仔细研究工厂的蓝图，当时《观察家》报的记者爱德华·克兰克肖就是其中的旁观者之一。“他好像变了一个人，不再是那个公众面前的小丑，那个恃强凌弱的煽动政治家，也不是那个喜欢卖弄的家伙了。……他所有的活力都集中于心头的工作上。”他的工作就是了解南斯拉夫建设的具体细节，教育南斯拉夫人懂得，能最好地指导经济发展的是工人委员会，而不是工厂经理与国家机构，“所有这一切都是在很平静但却是绝对权威的情况下完成的”。克兰克肖写道，在这种情况下，赫鲁晓夫“不用强调，也不用提高嗓门，就变成了一个天生的毫无争议的行家里手”。好像“那个空间里所有人的所有精力、所有生命力都被吸引进了这个矮小的身材里，他确切地知道他想要的是什么，而且能以最经济的努力方式达成他的目的。……”
但让铁托重新加入苏联集团则是另外一回事。在1955年剩下的时间与1956年上半年里，赫鲁晓夫加强他的示好努力。当然，最大胆的举动还是在苏共二十大上。他赞同实现社会主义可以有多种道路，其中就包括南斯拉夫的道路。他施加压力，让拉科什和其他东欧国家的斯大林主义者与铁托改善关系，并于1956年4月正式解散了共产党和工人党情报局，该机构曾被用作抨击贝尔格莱德的俱乐部，这些都给贝尔格莱德留下了印象。当铁托于1956年6月访问苏联时，军乐团和礼炮手在边境线上迎接他，在乌克兰的摩尔达维亚与莫斯科火车站，大批的群众夹道欢迎；在列宁格勒的大街上差不多有一百万人列队迎接；斯大林格勒热情的群众失去了控制，几乎将铁托和赫鲁晓夫挤倒。苏联领导人表现出了最好的姿态。在南斯拉夫大使馆的宴会上，甚至莫洛托夫也和其他人比赛，“看谁能用最尖刻的语言谴责斯大林的南斯拉夫政策”。
真正的谈判就不那么容易了。政府间的问题还是可以商量的：苏联人既没有责备铁托与西方国家的联系，也没有逼迫他承认东德。苏联的继续信任取决于南斯拉夫的“合作”，但赫鲁晓夫对此并没有反复强调。然而，让铁托承认彼此意识形态上的结合还是不可能的。在彻底完全的和解无望的情况下，赫鲁晓夫通过与铁托共同出席狄纳莫体育馆的一万人集会，想努力传达一种双方团结的印象。事实上，米库诺维奇说，俄罗斯人“真的很失望。他们对于此次访问投入了大量的心血，但他们的投资并没有得到回报”。
在接下来的四个月里，赫鲁晓夫的失望进一步加深了。没有对增强共产主义阵营的团结起到任何作用，难以驾驭的南斯拉夫反而加速了分裂的步伐。在波兰城市波兹南爆发罢工后不久，米库诺维奇在克里姆林宫的一次接待中发现赫鲁晓夫面色严峻。赫鲁晓夫抱怨说，在南斯拉夫出版他的狄纳莫体育馆讲话前，铁托进行了审查。他和他的同事“以最大的坦诚对待铁托”，得到的却是南斯拉夫人“以最粗鲁的方式破坏双方的协定”。赫鲁晓夫好像因为愤怒而无法控制自己的情绪。他不会“容忍任何人耍弄苏联的领导地位”。
米库诺维奇并不了解他所说的南斯拉夫媒体的“技术失误”，但苏联主席团却将《真理报》上的文章与南斯拉夫的报纸进行了逐句对照。冷静下来后，赫鲁晓夫说想进行这场争吵的不是他，而是他的同事。然而，不管怎么说，这件事情预示着苏南之间将会发生更多的纠葛。铁托并不只是维护其民族共产主义的称号，他还想将其传播到国外，特别是波兰与匈牙利。然而，如果赫鲁晓夫对铁托怀有第二种想法的话，那他得向主席团证明他的第一种想法是正确的。于是他努力对这位南斯拉夫领导人施加压力，给他看了苏联氢弹爆炸的“秘密”纪录片，并对他的助手施以大量哄诱与贿赂。那年的夏天与9月份，铁托被邀请去克里米亚和赫鲁晓夫一起“度假”，南斯拉夫人在苏联不管走到哪里，他们都会在卧室里发现窃听装置。尽管布尔加宁有失外交礼节地对南斯拉夫加以侮辱，但大量饮用伏特加是他们聚餐时的家常便饭。但在克里米亚最主要的内容还是在没有事先通知南斯拉夫人的情况下吉罗的突然出现，吉罗这个匈牙利顽固的斯大林主义者已经取代了拉科西，但不久他自己又被纳吉所取代。很显然，赫鲁晓夫的意图是想让南斯拉夫人与这位匈牙利党的新领导人修好，他们甚至在铁托事先没有同意的情况下宣布举行他们两人之间的会谈。