曼德拉在回忆跟海尔·塞拉西见面的情形时说：

他是一位让人印象深刻的人，真的，非常难忘。那是我第一次见到一位国家元首的礼节性动作。他穿着很正式的西装，身材瘦小，见到我们就弯腰鞠躬。但那并不能算作真正意义上的鞠躬，他一直直愣愣地站着，只点了一下头。接着，他坐下来和我们打招呼。会谈结束后，他召见了所有代表团的代表。奥利弗·坦博希望我代表大家跟他谈一谈。之后，我很简单地跟他介绍了一下南非国内的情况。他坐在沙发里，一动不动，就像一块木头，我也不知道他有没有听懂我的话。

后来，曼德拉在一次阅兵仪式上又见到了海尔·塞拉西。他当时正在给士兵颁奖，每颁一块奖牌，他就鞠躬致意。曼德拉感到很震撼，“那是我生平第一次看到黑人将军指挥下的黑人士兵受到来自世界各地的黑人领袖的欢呼和喝彩。那一刻，我多么希望这一幕能发生在我自己的国家里啊！”

很快，泛非自由运动大会就召开了。在会上，曼德拉用真名发表了一篇演讲，这篇演讲是在坦博和罗伯特·雷沙的辅助之下完成的。曼德拉讲述了南非政府对黑人施行的种种不平等法律，并呼吁世界各国对南非进行经济制裁。同时，曼德拉还强调，南非人民不能在自己国土之外寻求拯救：“南非自由民主斗争的核心和基石就在南非……南非民众将倾其全力发出迅猛有力的一击。”

随后，在半年多的时间内，曼德拉和坦博又相继访问了尼日利亚、埃及、利比亚、突尼斯、摩洛哥、马里、阿尔及利亚、利比里亚、苏丹、英国和塞拉利昂。一些新独立的非洲国家的领导人接见了他们，并答应给他们提供经济和军事上的援助。

在埃及，曼德拉第一次见到了大名鼎鼎的金字塔。他在日记中无比兴奋地写道：

虽然遭受到殖民者的掠夺，埃及这个国家依然保留了无比璀璨的古代艺术和文化。我很早就渴望能够到埃及参观金字塔和狮身人面像，再看看拉姆西斯二世的木乃伊。在埃及所有的法老中，拉姆西斯二世的权力最大。整个上午，我都在博物馆里作笔记，而且作得很详细。之后，奥利弗·坦博带我去了吉萨，大名鼎鼎的金字塔就坐落在那里。整座金字塔是巨型石头结构，上下都是方形基座，与地面连接得很结实，三个斜面的顶部连接在一起构成金字塔的姐姐。整座金字塔由灰泥和巨大的石块构成，另外还有一座同样用灰泥和石块构成的纪念碑式的建筑物。金字塔和这座建筑物背负着各自的重量屹立了上千年。

参观完金字塔后，我们去乘船，准备环绕这个岛屿在尼罗河上游览一圈。一个9岁的男孩熟练地为我们划船，奥利弗·坦博惊奇地说：“这个小男孩能划船？不会吧？”在说话的同时，他还往后退了一步，站在船上比较安全的地方。后来，船夫换成了一名年纪比较大的男子，我们才放心下来。

早在公元5000年前，尼罗河的文明就开始兴盛了。而我感兴趣的是，到底是什么样的人才能缔造出这么璀璨的文明呢？白人们经常鼓吹说：“世界文明起源于我们欧洲，非洲的古代文明根本比不上我们的！”非洲的一些思想者总是习惯寻找科学的证据来驳斥这种谬论，而这种习惯已经成为了他们的重任之一。我对尼罗河文明缔造者的兴趣正源于此。当时，我与博物馆的一个馆长探讨了一下这个问题，他的回答很谨慎。他提出的一些理论我也很感兴趣，同时我也很感激他回答我的问题。但是，在离开博物馆的时候，我并没有觉得我的知识有所增长。

在阿尔及利亚，曼德拉看到游击队员们正在欢迎他们的民族解放领袖阿哈迈德·本·贝拉归来。阿哈迈德刚从监狱获释，并马上当选为阿尔及利亚独立后的第一任总统。阿哈迈德告诉曼德拉，只要非洲还在帝国主义的控制之下，阿尔及利亚的自由就没有意义。

随后，阿哈迈德邀请曼德拉视察部队。正如曼德拉讲的：“我看到阿尔及利亚青年的精英，他们曾与法国帝国主义进行斗争，以他们的勇敢换来了他们国家的自由和幸福。”

在塞拉利昂，也发生了一段很有意思的故事。当曼德拉走进会议大厅的时候，发现他们正在开会。于是他只好轻轻地走到工作人员的身边，小声说：“我是南非鲁图利酋长的代表。”工作人员听后非常高兴，马上给曼德拉安排了一个上等的座位。

会议结束后，曼德拉奇怪地发现有很多人排着队要和他握手，这让他受宠若惊。当握到第4只手的时候，那人对他说：“与诺贝尔和平奖的获得者——尊敬的鲁图利酋长握手真是一种莫大的荣幸。”曼德拉这才意识到他们把自己当成了鲁图利酋长。曼德拉赶忙跟他们解释，但工作人员根本不听他的解释，他就只好将错就错下去了。

在去过了这么多国家后，曼德拉充分意识到组建军队的重要性，于是他决定回到埃塞俄比亚，接受军事训练，为领导“民族之矛”做准备。