1961年底，非洲人国民大会收到非洲东非、中非和南非泛非自由运动组织的邀请，派重要领导人参加1962年2月在埃塞俄比亚首都亚的斯亚贝巴召开的泛非自由运动大会。非洲人国民大会经过慎重考虑，最终决定派曼德拉前去参加会议，并向非洲其他地区求助以解决资金和培训问题。
临行前，曼德拉去南塔尔省看望了鲁图利酋长。鲁图利同意曼德拉的出行计划，并提出：“如果非洲人国民大会有新的动向，我希望你们能征求我的意见。”
晚上，曼德拉又去见了自己的妻子温妮。他们已经有好几个月没有见面了。得知曼德拉要出国时，温妮显得特别担心，她一遍又一遍地嘱咐曼德拉，要他多注意休息。曼德拉回忆说：“那天，我们聊了一夜，她拒绝和我亲热。她的行为与其说像是我的夫人，倒不如说更像是一名战士。”
1962年1月10日，曼德拉和温妮道别，驾车越过国界来到了贝专纳兰（现在的博茨瓦纳）。当时，贝专纳兰是英国的保护国。一到贝专纳兰境内，曼德拉就喜欢上了美丽的异族风情。后来他在回忆录中写道：“我看到了更广阔的非洲，还亲眼看到母狮子从路上穿过。”
接着，曼德拉与朋友乔·马修斯又从贝专纳兰包机前往坦桑尼亚的首都达累斯萨达姆。在乘飞机的时候，出了一点小插曲。曼德拉回忆说：“那次不是我第一次坐飞机，但是，还是很惊险。我们遇到了风暴，机舱内一片混乱，人们都很不安。后来好不容易飞到了机场附近，飞机跑道又被水淹了。飞机抵达时，成群的大象和其他动物都在那里吃草，根本无法降落。最后，飞机只好转向，去其他地方降落……”
当曼德拉置身于坦桑尼亚时，他第一次发现白人和黑人可以平等相处。
我置身于一个非洲人当政的国家，我生平第一次成为一个自由的人。尽管我是一个在自己的土地上被通缉的逃犯，但是，我感觉到压在我肩膀上的那副重担忽然消失了。在这里，我的肤色不再成为别人的笑谈。我也第一次意识到，衡量我个人好坏的标准并不是根据肤色，而是根据我内在的修养和品质。我曾无数次想要回家，但是，我感觉到我第一次真正地回到了家。
然后，曼德拉又从坦桑尼亚飞到加纳的阿克拉机场，在那里，他见到了老朋友奥利弗·坦博。此时，两人已经有两年多没有见面了。当曼德拉走下飞机见到坦博的时候，他几乎不能相信自己的眼睛，因为眼前的那个人不修边幅、穿着随意，根本不像以前那个穿着整齐、风度翩翩的坦博。两人惊讶地互相注视了一会儿，然后兴奋地抱在了一起。
在加纳，曼德拉受到当地行政部长的接见。曼德拉向他提出5000美元的援助。行政部长彬彬有礼地说：“加纳政府和加纳人民是完全支持我们的南非同胞的。”然后，他从桌子上拿起两本书，签上自己的名字，送给曼德拉和坦博。曼德拉和坦博两人目瞪口呆：他们千里迢迢地来这里，得到的援助居然只是两本书！两人只好闷闷不乐地回到了宾馆。
刚到宾馆，一个外交官员便给他们送来一个箱子。两人打开一看，居然是满满一箱钱！两人惊喜莫名，但随即坦博的笑容便僵在了脸上，他对曼德拉说：“这是加纳钱币，一旦离开加纳，这些东西就相当于一堆废纸。”不过，这也没有难倒两人，坦博找到了自己在加纳的朋友，把这一箱钱都换成了美元。
1962年2月，曼德拉和坦博又飞往埃塞俄比亚的首都亚的斯亚贝巴参加泛非自由运动大会。在乘坐飞机的时候，曼德拉发现了一个黑人飞行员。在此之前，他从来没有见过黑人飞行员。曼德拉的第一反应是：“黑人怎么可以当飞行员呢？”
在埃塞俄比亚，曼德拉第一次见到了被誉为“雄狮之主”的埃塞俄比亚皇帝海尔·塞拉西。曼德拉很小的时候就听说了这位传奇统治者坚决抵抗意大利侵略的事迹。
海尔·塞拉西1930年即位，带着斑马和狮子周游欧洲列国，回国后奋发图强，改革埃塞俄比亚。1931年，海尔·塞拉西颁布了帝国宪法，仿效西方设参、众两院，但同时又规定了至高无上的皇权。1935年10月，意大利入侵埃塞俄比亚，海尔·塞拉西领导抗战。后来他一度流亡国外，直到1941年复国，其间过程跌宕起伏。海尔·塞拉西虽然战术上有所失误，但始终不肯屈服，堪称一代“雄狮之主”。在卫国战争中，海尔·塞拉西将身边的王子一个接着一个派回埃塞俄比亚领导游击战争，这些王子也都尽忠职守，在和意军的战斗中全部壮烈殉国，无一投降。1941年，在英军的帮助下，埃塞俄比亚终于击败意大利，复国成功，皇帝的威望也上升到新的高度。
曼德拉在回忆跟海尔·塞拉西见面的情形时说：
他是一位让人印象深刻的人，真的，非常难忘。那是我第一次见到一位国家元首的礼节性动作。他穿着很正式的西装，身材瘦小，见到我们就弯腰鞠躬。但那并不能算作真正意义上的鞠躬，他一直直愣愣地站着，只点了一下头。接着，他坐下来和我们打招呼。会谈结束后，他召见了所有代表团的代表。奥利弗·坦博希望我代表大家跟他谈一谈。之后，我很简单地跟他介绍了一下南非国内的情况。他坐在沙发里，一动不动，就像一块木头，我也不知道他有没有听懂我的话。
后来，曼德拉在一次阅兵仪式上又见到了海尔·塞拉西。他当时正在给士兵颁奖，每颁一块奖牌，他就鞠躬致意。曼德拉感到很震撼，“那是我生平第一次看到黑人将军指挥下的黑人士兵受到来自世界各地的黑人领袖的欢呼和喝彩。那一刻，我多么希望这一幕能发生在我自己的国家里啊！”
很快，泛非自由运动大会就召开了。在会上，曼德拉用真名发表了一篇演讲，这篇演讲是在坦博和罗伯特·雷沙的辅助之下完成的。曼德拉讲述了南非政府对黑人施行的种种不平等法律，并呼吁世界各国对南非进行经济制裁。同时，曼德拉还强调，南非人民不能在自己国土之外寻求拯救：“南非自由民主斗争的核心和基石就在南非……南非民众将倾其全力发出迅猛有力的一击。”
随后，在半年多的时间内，曼德拉和坦博又相继访问了尼日利亚、埃及、利比亚、突尼斯、摩洛哥、马里、阿尔及利亚、利比里亚、苏丹、英国和塞拉利昂。一些新独立的非洲国家的领导人接见了他们，并答应给他们提供经济和军事上的援助。
在埃及，曼德拉第一次见到了大名鼎鼎的金字塔。他在日记中无比兴奋地写道：
虽然遭受到殖民者的掠夺，埃及这个国家依然保留了无比璀璨的古代艺术和文化。我很早就渴望能够到埃及参观金字塔和狮身人面像，再看看拉姆西斯二世的木乃伊。在埃及所有的法老中，拉姆西斯二世的权力最大。整个上午，我都在博物馆里作笔记，而且作得很详细。之后，奥利弗·坦博带我去了吉萨，大名鼎鼎的金字塔就坐落在那里。整座金字塔是巨型石头结构，上下都是方形基座，与地面连接得很结实，三个斜面的顶部连接在一起构成金字塔的顶点。整座金字塔由灰泥和巨大的石块构成，另外还有一座同样用灰泥和石块构成的纪念碑式的建筑物。金字塔和这座建筑物背负着各自的重量屹立了上千年。
参观完金字塔后，我们去乘船，准备环绕这个岛屿在尼罗河上游览一圈。一个9岁的男孩熟练地为我们划船，奥利弗·坦博惊奇地说：“这个小男孩能划船？不会吧？”在说话的同时，他还往后退了一步，站在船上比较安全的地方。后来，船夫换成了一名年纪比较大的男子，我们才放心下来。
早在公元5000年前，尼罗河的文明就开始兴盛了。而我感兴趣的是，到底是什么样的人才能缔造出这么璀璨的文明呢？白人们经常鼓吹说：“世界文明起源于我们欧洲，非洲的古代文明根本比不上我们的！”非洲的一些思想者总是习惯寻找科学的证据来驳斥这种谬论，而这种习惯已经成为了他们的重任之一。我对尼罗河文明缔造者的兴趣正源于此。当时，我与博物馆的一个馆长探讨了一下这个问题，他的回答很谨慎。他提出的一些理论我也很感兴趣，同时我也很感激他回答我的问题。但是，在离开博物馆的时候，我并没有觉得我的知识有所增长。
在阿尔及利亚，曼德拉看到游击队员们正在欢迎他们的民族解放领袖阿哈迈德·本·贝拉归来。阿哈迈德刚从监狱获释，并马上当选为阿尔及利亚独立后的第一任总统。阿哈迈德告诉曼德拉，只要非洲还在帝国主义的控制之下，阿尔及利亚的自由就没有意义。
随后，阿哈迈德邀请曼德拉视察部队。正如曼德拉讲的：“我看到阿尔及利亚青年的精英，他们曾与法国帝国主义进行斗争，以他们的勇敢换来了他们国家的自由和幸福。”
在塞拉利昂，也发生了一段很有意思的故事。当曼德拉走进会议大厅的时候，发现他们正在开会。于是他只好轻轻地走到工作人员的身边，小声说：“我是南非鲁图利酋长的代表。”工作人员听后非常高兴，马上给曼德拉安排了一个上等的座位。
会议结束后，曼德拉奇怪地发现有很多人排着队要和他握手，这让他受宠若惊。当握到第4只手的时候，那人对他说：“与诺贝尔和平奖的获得者——尊敬的鲁图利酋长握手真是一种莫大的荣幸。”曼德拉这才意识到他们把自己当成了鲁图利酋长。曼德拉赶忙跟他们解释，但工作人员根本不听他的解释，他就只好将错就错下去了。
在去过了这么多国家后，曼德拉充分意识到组建军队的重要性，于是他决定回到埃塞俄比亚，接受军事训练，为领导“民族之矛”做准备。