在匈牙利、罗马尼亚和保加利亚领导人的陪同下（此外，还有乌克兰与白俄罗斯的领导人，斯大林于1945年默许两加盟共和国可以作为独立的国家参加联合国会议），赫鲁晓夫于9月9日晚上从位于波罗的斯克的一个苏联海军基地出发（离原东普鲁士城市柯尼斯堡不远）。这艘性能良好的“波罗的海号”舰船是荷兰人于1940年在阿姆斯特丹为德国人建造的，二战后被苏联人作为战利品缴获，被重新命名为“维亚切斯拉夫·莫洛托夫号”，后来在“****集团”于1957年被打倒后又重新更换了名称。赫鲁晓夫对他第一次也是唯一的一次越洋航行的回忆既有担忧，也有愉悦的经历。他的担忧主要是可能在纽约会受到不友好的接待，而他的愉悦则来自可以将工作（阅读形势报告，与东欧国家领导人进行磋商）与游戏（推圆盘游戏，不时地对那些晕船的人开玩笑，赫鲁晓夫自己不晕船），结合在一起以及那种“被一望无际的海水所包围”的“新鲜而罕有的感觉”。
当他们坐在甲板的椅子上时，一群专家与助手开始轮流给赫鲁晓夫宣读关于国际事务的情报材料。其中的一名助手德米特里·高里尤诺夫记得赫鲁晓夫“在舰船上表现得很冷静。他没有发脾气，尽管他是个很爱冲动的人”。但是，当赫鲁晓夫口授指示，将外交部在莫斯科为他准备的发言稿修改得态度更为强硬时，葛罗米柯感到很担心。赫鲁晓夫说：“对美国单方面行动的批评措词要更加激烈一些。……有必要考虑将联合国总部搬到瑞士、奥地利或是苏联。……对付美国人……就是要打落他们的牙齿，然后说：‘对不起，我不是故意的。你得从我们的角度来看，我不得不这么做，因为你把牙齿露出来了。’”
在漫长的旅行中，赫鲁晓夫经常与水兵们在一起，给他们讲故事与笑话。当东欧国家领导人在酒吧间没完没了地打牌时，赫鲁晓夫宁愿去看电影，不过他会和他们一起去观看水兵们的业余消遣活动，特别是和他的好朋友，匈牙利领导人亚诺斯·卡达尔一起喝上几杯。当他的高级助手们因为晕船而躺在他们的舱室，稍低级别的官员围着女招待员与打字员转时，赫鲁晓夫就与苏联低级别的外交人员阿卡迪·谢甫琴科一起消磨时间。赫鲁晓夫感叹对西方文学没有什么了解，不过他开玩笑地说那还不如学好一门外语，“对我而言，掌握好俄语会更有用”。在谈到如何与西方国家领导人打交道时，他盼望着有关全面彻底裁军的宣传会软化他们在军控谈判中的立场。“每种蔬菜都有它自己的生长季节。”他和蔼地告诉谢甫琴科说。
“波罗的海号”于9月19日驶入纽约港。与赫鲁晓夫一年前胜利抵达安德鲁空军基地相比，这是多大的落差啊！舰船的甲板在航行途中进行了重新粉刷，其他的地方也都打扮一新，就为了能在到达美国时给世人留下一个深刻的印象。但是，当他们进入港口时，受到了国际码头工人工会示威者的“欢迎”，他们租来了一条观光船，手持标语牌：红色的玫瑰，紫色的紫罗兰，斯大林已经死了，那么你呢？亲爱的赫鲁晓夫！去死吧，你这个混蛋！
“他们全都穿着古怪的服装，”赫鲁晓夫在回忆录中写道：“朝我们挥动标语牌，举起像稻草人那样的东西，并通过扩音器向我们喊口号。我们全都走到甲板上来，指着他们笑。对我们而言，示威是美国侵略势力上演的一场化装丑剧。”
如果说这种“欢迎”是令人不快的，那73号码头的情况则更糟：这是一个位于东河上的破烂不堪的码头。《真理报》记者瓦西里耶夫在苏联代表团还没有到达时已经起草好了他的报道文章：早上阳光明媚；欢乐的人群在码头上列队欢迎；每个人手里都挥舞着鲜花。实际上，“波罗的海号”徐徐驶入港口时，天上下着大雨，除了苏联官员和他们的家人、记者以及警察与安全人员外，只有匈牙利流亡示威者在那里“迎接”这位共产党领导人。由于码头工人工会的示威者抵制“波罗的海号”靠岸，舰船上的水兵只好放下救生筏，然后将救生筏固定在码头上，而外交人员只好自己将行李费力地搬下来。同时，至少有一名船员叛逃。
谢甫琴科认为，苏联驻美国与联合国大使应该为这种悲惨的抵达场面负责，他们过于机械地领会了莫斯科关于不要把钱浪费在租用码头上的指示。实际上，是赫鲁晓夫本人发出的指令。他“极为愤怒”，赫鲁晓夫后来说，他深信“美国人让我们停靠如此破烂的码头是想作弄俄国人”，但是他“并不想去寻找替罪羊。我只能责怪自己。”赫鲁晓夫在他的回忆录中说。
然而，当他于早上9时48分走下跳板时，赫鲁晓夫还是努力装出兴高采烈的样子，他脚下的那块极富东方特色的垫子就像一块巨大的海绵一样吸干了雨水。他在码头所发表的讲话中以挑战的口吻建议艾森豪威尔总统和他在联合国大会期间举行临时的首脑会晤。在《真理报》上发表前，瓦西里耶夫设法将阳光明媚的词句删除了，但保留了码头上簇拥着欢乐的人群的描述。
赫鲁晓夫在纽约一直呆到了10月13日，然后乘飞机回到莫斯科。前后加在一起，他离开克里姆林宫超过了一个月的时间。即使根据他自己喜欢到处游历的标准，此次离开的时间也是令人惊讶的太长了。很显然，他对让其他人在国内主持事务有足够的安全感。但是他对自己所认为的使命太过迷恋了，他在联合国大会上为共产党国家的事业进行了大量的发言。
在纽约，赫鲁晓夫就像苦行僧一样到处奔波。他发表了几次长篇演讲，并积极参加联合国的辩论。在曼哈顿以及苏联代表团在长滩格伦科夫的驻地，不管白天黑夜，只要需要，赫鲁晓夫会随时举行记者招待会。他与世界各国领导人拥抱，在正式的午宴与晚宴上发表讲话，并出现在大卫·索斯金德的电视节目里。他也制造了一些骚乱，有一次在没有告知警察与安全人员的情况下（为了显示他有权利在纽约市自由活动），他来到哈莱姆（纽约贫困黑人居住区）看望菲德尔·卡斯特罗，在特里萨饭店拥挤的走廊里与卡斯特罗热情拥抱。站在位于公园大街与68号大街交汇处的苏联代表团驻地二楼的阳台上，赫鲁晓夫曾对下面聚集的记者，嘴里哼出“国际歌”的曲调。当一位新闻记者提醒他在红色墙壁的衬托下，他的白衬衣会成为很好的攻击目标时，赫鲁晓夫昂首挺胸，右手挥舞着拳头，向空中做出斩钉截铁的姿势。
苏联的媒体当然将所有这些都描述成赫鲁晓夫取得的胜利，他在回国后也是这么表示的。“他认为自己是胜利者，”他儿子写道，认为联合国大会“为巴黎首脑会晤的失败做出了补偿”。但是赫鲁晓夫在纽约的言行不能只说成是夸张而古怪，实际上显得很奇异。当联合国秘书长哈马舍尔德在联合国大会上发言时，赫鲁晓夫用拳头敲击桌子表示抗议，直到后来葛罗米柯（经过一番犹豫后）、苏联代表团里的其他成员以及最后所有其他共产党国家的代表团都加入这一行列。当英国首相麦克米伦公开对巴黎首脑会晤的失败表示遗憾时，赫鲁晓夫跳起来喊道：“是你们将飞机飞到了我们的领空，你们的侵略行动应该受到惩罚！”并再次挥舞胳膊，用拳头敲击桌子。麦克米伦转过头来向联合国大会轮值主席，爱尔兰的弗雷德里克·H.布兰德提出抗议说，如果赫鲁晓夫先生继续这样下去，他希望他能作出解释。布兰德敲槌要求赫鲁晓夫保持会场秩序，那一天赫鲁晓夫没有再作出干扰会议的行为。
10月11日，当他向大会做完发言回到座位上时，赫鲁晓夫突然注意到西班牙人没有鼓掌。他用手指着一位西班牙年轻代表的脸，用俄语大声咒骂，并好像随时准备上去对那位外交使节拳打脚踢似的。在联合国与苏联安全人员走上前后，这位苏联领导人才稍稍平息了怒气。
最值得一提的就是那个著名的敲皮鞋事件，这发生于赫鲁晓夫在纽约的最后一天。一位菲律宾代表在讨论非殖民地化的问题时指责莫斯科说，东欧“被剥夺了政治与民权”，“实际上是被苏联吞并了”。在用双手敲击桌子后，脸色涨得通红的赫鲁晓夫脱下他右脚上的皮鞋（根据谢尔盖的说法，那是一种矮腰的便鞋，因为赫鲁晓夫不喜欢系鞋带），示威性地挥舞着，然后干脆在桌子上敲打起来，声音越来越大，直到会场上所有的人都看着他议论纷纷。[24]坐在赫鲁晓夫旁边的葛罗米柯表情十分痛苦。带着“痛苦的抉择”以及那种“像将要跳入一池冰水的那种表情”，这位外交部长也脱下了他的鞋子，开始在桌子上轻轻地敲打起来，好像希望他的主人能看到，而其他人看不到似的。[25]
赫鲁晓夫对他自己的表现洋洋自得。得知特罗亚诺夫斯基没有看到那一幕时，赫鲁晓夫告诉他说：“噢，你真正错过了一场好戏！太有趣了！你知道，联合国就像某些议会一样，少数派必须依靠这样或那样的方法来使人们听到他们的声音。我们暂时处于少数派的地位，但时间不会太长。”其他人对此并没有留下太深的印象。白俄罗斯共产党领导人基里尔·马祖罗夫觉得这让人感到“很尴尬”。根据谢甫琴科的说法，会议结束后在苏联代表团的驻地，“所有的人都感到困窘与沮丧”。一向要求严格、不做错事的葛罗米柯“气得嘴唇发青。但是赫鲁晓夫好像什么事情都没有发生一样。他仍然大声地笑着，不时开个玩笑。他说有必要‘给联合国沉闷的气氛注入一丝生气了’”。
当天晚上，向来以机智幽默著称的匈牙利领导人卡达尔在与赫鲁晓夫共进晚餐时找到了一种微妙的办法表达他的不满：“赫鲁晓夫同志，你还记得你在用鞋子敲打桌子后不久走上讲坛要求保持会场秩序吗？就在那个时候，我们的外交部长，西克同志，转过身来对我说：‘你认为他有时间穿上鞋子吗？他是光着脚走上去的？’”特罗亚诺夫斯基写道：“很多坐在会场里的人都开始窃笑。我有一种感觉，就是我们的领导人当时已经意识到他也许做得太过分了。”
根据赫鲁晓夫儿子的说法，这种怪异的举动让苏联代表团成员也大吃一惊，当赫鲁晓夫于1964年被赶下台时，这被他的对手当作反对他的理由之一，而且很多俄罗斯人至今仍对此耿耿于怀，其实这是一种精心策划的姿态，赫鲁晓夫是从大革命前俄罗斯杜马会议上学来的，他认为西方国家的立法会议上仍然会出现这样的情况。[26]但是不管怎么说，这也是一种恶劣的表现，反映了他不能控制自己的情绪。当联合国大会同意讨论非殖民地化问题时，赫鲁晓夫很是满意，但当大会以压倒性多数投票决定将他的裁军提议归由一个更低一些的政治委员会讨论时，他又暴怒起来。他紧张地关注着刚果的局势（在刚果，苏联支持的卢蒙巴处于亲西方的冲伯与蒙布图的包围之下），并对他所认为的联合国的反卢蒙巴偏见很是恼火。“我对联合国没有好感，”在特罗亚诺夫斯基向他报告了一些来自刚果的坏消息时，赫鲁晓夫在“波罗的海号”上咆哮说：“联合国不是我们的组织。那个一无是处的哈马［俄罗斯人对哈马舍尔德的轻蔑称谓］对于本与他无关的重要事务总是想窥视、插手。我们真的要给他点厉害看看。”
赫鲁晓夫要求应由三名官员（这三驾马车由一位西方人、一位共产主义阵营的代表以及一个来自中立国家的代表组成）来取代联合国秘书长的职权，而且联合国应该将总部搬到欧洲——瑞士或是奥地利，甚至也可以设在苏联。但是这些愚蠢而滑稽的改革会削弱联合国作为论坛的分量，而赫鲁晓夫当时已经选择这一论坛作为他谋求利益的场所，同时这也有违苏联反对对《联合国宪章》进行任何修改的长期政策。他的这些提议不仅遭到了联合国大多数成员国的反对，美国外交人员马上站起来表示反对，而且就连赫鲁晓夫自己的代表团中也有人反对。“赫鲁晓夫突然之间开始坚持他的三驾马车的想法，”当时在苏联外交部任职的乔治·科尔年科记得：“这是他自己的想法，西方国家是无论如何也不会接受的。从实质上来看，这是一种没有希望、不切实际的想法，这就是当时我们很多人对此的看法。他继续提出这些问题是另外一回事，从常识来看，他的这些想法也是奇怪、不可理解的。”[27]