南斯拉夫的社会性质一经确认，“斯大林据以在两国间制造争论的基础就不再有效，反对同南斯拉夫和解的论点就像纸牌搭的房子一样倒坍了。”（注：《赫鲁晓夫回忆录》，东方出版社1988年版，第544 页。）鉴于1953年6月14 日铁托在《关于与苏联关系正常化的声明》中发表的“互换大使并不一定意味两国关系的正常化或两国关系的改进，因为势不两立的敌人也会互换外交官员”的谈话（注：斯蒂芬·克利索德编：《1939-1973年南苏关系（文件与评注）》，人民出版社1980年版，第453页。），赫鲁晓夫感到有必要进一步采取实际行动， 以改善两国关系。
    1954年6月22日，苏共中央给南共联盟中央发来了1948 年中断关系以后的第一封信，表示愿意同南斯拉夫改进关系。8月11日， 铁托回信表示：“有鉴于痛苦的经验，光发表口头的或者书面的声明还不够，还要有事实。”（注：兹冯科·施陶布林格：《铁托的独立道路》，新华出版社1987年版，第126页。）为此，同年10月20 日《真理报》就贝尔格莱德解放10周年发表文章，一改过去认为南斯拉夫是“军事法西斯专政国家”的指责，赞扬苏南人民之间存在着“用鲜血凝成的”友谊（注：罗伊·梅德韦杰夫：《赫鲁晓夫政治生涯》，社会科学文献出版社1991年版，第58-59页。）。11月28日，南斯拉夫驻苏大使馆为纪念独立日举行招待会，“苏联领导人几乎全部出席”（注：罗伊·梅德韦杰夫：《赫鲁晓夫政治生涯》，社会科学文献出版社1991年版，第59页。）。鉴于日渐形成的友好氛围，怎样同铁托直接接触才是最佳方式问题被提上议事日程。强硬派提出，应当要求南斯拉夫领导人到莫斯科来谈判，但赫鲁晓夫否决了这一建议，而“赞成作一个史无前例的姿态，到贝尔格莱德进行访问”（注：斯蒂芬·克利索德编：《1939-1973年南苏关系（文件与评注）》，人民出版社1980年版，第139页。）。他解释说：“第一，我不相信他们会接受邀请。这会显得是他们恭恭敬敬地来乞求我们；第二，是我们主动断绝了同他们的关系；是我们在他们攻击我们之前就公开攻击了他们。因此，应该由我们采取主动来结束分裂；第三，我们是大国、大党，在共产主义世界享有崇高的权威和威望。万一南斯拉夫人到我们领土上来会见我们而又不能达成一项协议的话，他们要冒很大的风险。”（注：《赫鲁晓夫回忆录》，第545页注①。 ）主动与南接触的方式确定后，赫鲁晓夫向铁托提出了访问建议，后者表示：“同意接待”（注：《赫鲁晓夫回忆录》，第545页注①。）。1955 年5月14日， 莫斯科发表了苏共中央第一书记赫鲁晓夫即将亲自率领苏联政府代表团访问南斯拉夫的公报。公报称：“基于进一步改善两国关系和巩固和平的共同愿望，两国政府同意举行一次最高级会晤。”（注：杰弗里·巴勒克拉夫等：《国际事务概览（1955-1956年）》，上海译文出版社1985年版，第171页。）次日，铁托在普拉发表谈话， 对不久举行的会谈“表示欢迎”（注：兹冯科·施陶布林格：《铁托的独立道路》，新华出版社1987年版，第145页。）。不过， 当时铁托对于苏南修好也不是毫无顾虑。他主要是“担心由此会影响他同西方国家的关系”（注：杰弗里·巴勒克拉夫等：《国际事务概览（1955-1956年）》，上海译文出版社1985年版，第171页。）。故此， 他预先向西方国家及希腊和土耳其的大使们通报了苏联领导人即将来访，同时极为坚决地保证：“南苏会谈决不影响南斯拉夫的外交政策”（注：[英]《泰晤士报》，1955年5月16日。）。鉴于此，《真理报》在5月18日承认两国“对于社会发展的一些重要问题在理解上有重大分歧”的同时强调指出，同苏联恢复正常化关系，“决非，并且也不可能意味着南斯拉夫同其他国家的关系恶化”。重要之点是，“苏联人民同南斯拉夫人民之间是存在着进行广泛和全面合作的坚实基础的。”苏方显然愿意将意识形态问题搁置不谈的意图，得到了贝尔格莱德方面的称赞，铁托总统欢迎这一“勇敢的决定”，说它将使这次访问成为近来苏联一系列行动中“最具有积极意义的一个行动。”（注：杰弗里·巴勒克拉夫等：《国际事务概览（1955-1956年）》，上海译文出版社1985年版，第171-172页。）
    1955年5月26日，赫鲁晓夫率领由苏联部长会议主席布尔加宁、 第一副主席米高扬、《真理报》主编谢皮洛夫和外交部第一副部长葛罗米柯、外贸部副部长库米金等组成的苏联代表团飞抵南斯拉夫首都贝尔格莱德，同以铁托为首的南斯拉夫代表团举行会谈。值得注意的是，当时仍担任外交部长的莫洛托夫未能同行。
    由于多年来南斯拉夫党和政府受到巨大困难和压力，南共领导对苏共的大国主义和大党主义存在戒心，对苏联新领导人的诚意也有所怀疑，因而在机场，苏联代表团虽受到了南方“应有的一切礼遇”。但是，“看不到有任何兄弟般的感情”（注：《赫鲁晓夫回忆录》，第545 页注①。）。在欢迎仪式上，赫鲁晓夫宣读了一份由苏共中央领导集体草拟的负荆请罪式的声明。他在声明中承认，苏方对过去两国关系中“发生的一切衷心地感到遗憾，并且决心要消除这个时期中的一切芥蒂。”他表示相信，“在苏南关系中笼罩阴影的那个时期已经过去了”，“愿意尽力消除”阻碍两国关系完全正常化、阻碍两国人民友好关系巩固的一切障碍（注：赫鲁晓夫：《赫鲁晓夫言论》第4集（1955年）， 世界知识出版社1965年版，第236页。）。他说， 他对南斯拉夫要同西方和东方所有国家发展关系的愿望表示“完全理解”，相信苏南之间友谊和联系的加强，“将有助于改善所有国家（不问它们社会制度如何）之间的关系，将有助于巩固普遍和平。”如果两国领导人不尽一切可能来求得苏南之间的互相谅解，那么就是没有对两国人民和全世界劳动人民“尽到自己的责任”（注：赫鲁晓夫：《赫鲁晓夫言论》第4集（1955年），世界知识出版社1965年版，第237页。）。
    当赫鲁晓夫宣读上述《声明》时，铁托总统作为东道主“脸上毫无笑容，表情严峻”（注：菲利斯·奥蒂：《铁托传》，黑龙江人民出版社1979年版，第301页。）。对赫鲁晓夫等来访并未致欢迎词， 只对客人说：“你看，我们用不着把你的讲演译出来，在场的人都懂俄语。”（注：《赫鲁晓夫回忆录》，第545-546页注①。）事实上，并非所有在场的南斯拉夫人都懂俄语。所以，赫鲁晓夫对于访问一开始受到如此冷淡接待，“有些失望”（注：《赫鲁晓夫回忆录》，第546页注①。）。