在这里，我生平第一次感到自己是个自由人。尽管我在自己的国家里正在遭受通缉，但此刻我的恐惧和压力全部消失了。在这里，我的肤色被所有人自然地接受，我第一次意识到衡量我好坏的并非我的肤色，而是我的内在品质。
——曼德拉狱中日记
在非国大被正式取缔不久后，曼德拉等人就将以奥利弗为首的几位重要领导人送到了国外，在争取其他非洲兄弟支持的同时，也为非国大保存重要的有生力量。曼德拉为了继续领导国内的斗争，便坚定地留了下来，并声称自己不会出国。
但经过这次爆炸事件，一来政府加紧了对曼德拉的搜捕，他成为政府的头号通缉犯，二来曼德拉也发现了寻求国际支援的迫切性。这次爆炸事件完全没有伤到政府的筋骨，民族之矛还因为人员经验不足损失了一名成员。因此，他们迫切需要其他国家包括物资和人员在内的军事支援。而在此时，非国大恰好接到泛非自由运动组织的邀请，要派一名领导人去参加在埃塞俄比亚首都举行的大会。他们便打算让曼德拉去参加这次会议，顺道寻求非洲和欧洲一些国家的支持。
这次出国的经历对曼德拉来说十分重要，离开了南非，他才发现黑人获得自由并非妄想，有许多国家早已实现了黑人自治。在坦葛尼喀，曼德拉第一次看到黑人可以和白人坐在一起毫无障碍地交流，黑人的嘴里没有卑怯，白人的眼中也没有骄傲。在当地的宾馆里，甚至有一位黑人客人责备白人服务员怠慢了自己。在这里，他第一次感到自己作为非洲人是自由的。他虽然很想念南非的家，但在这里，他感觉自己第一次真正回了家。
坐飞机时，曼德拉还遇到一个黑人飞行员。他的第一反应是：黑人怎么可以当飞行员呢？这种在白人的奴化教育下养成的思维习惯让曼德拉感到羞愧。同时，他也进行了反思：连非国大的重要领导人都在潜意识里有这种观念，更何况那些遭受压迫的黑人同胞呢？越看到周边国家的自由和民主，曼德拉越感到肩上的责任重大。这使得他在接下来的一段时间里，不遗余力地投入游说的行动中。
在加纳，曼德拉和奥利弗重逢了。在奥利弗流亡在外的两年里，他在英国、埃及和加纳等地建立了非国大的办事处。凭借优秀的口才，他为非国大在国际上赢得了一个较好的名声。但是他同时告诉曼德拉，非国大在国际上的地位居然低于激进的阿扎利亚泛非洲主义者大会。虽然沙佩维尔惨案暴露出泛非洲主义者大会的激进与幼稚，但他们在游说和诋毁对手上的本事十分高超。他们利用沙佩维尔惨案在国际上的影响力，将自己塑造成一个勇敢不屈的伟大组织。同时，他们还不遗余力地诋毁非国大，说非国大是由共产党和印度人控制的。由于非洲其他独立国家都是黑人当权，并没有南非这种多人种混居的状况，所以这些国家的领导人在泛非洲主义者大会的蛊惑下对非国大十分警惕。这也为曼德拉和奥利弗的这次游说增添了难度。
对此，曼德拉做了两手准备，一是详细地解释南非的人口构成现状，将其斗争的复杂性以尽量清晰的方式表达出来，二是坚定地表明非国大是一个由非洲人领导的组织，以争取更多的同情和支持。
首先，他们来到了大会的举办地：埃塞俄比亚的首都亚的斯亚贝巴。埃塞俄比亚对非洲人来说是一个朝圣的地方，这里是非洲民族主义的发源地，作为一个非洲人，曼德拉可以在这里找到自己的起源。在这里，曼德拉幸运地见到了“犹大之狮”埃塞俄比亚皇帝：海尔·塞拉西。近70岁的他正在检阅一支黑人军队，这个场面再次震撼了曼德拉。他希望这样的场面也能早日出现在自己的国度。
在大会上，曼德拉发表了自己政治生涯里颇为重要的一次演讲，他在演讲中控诉南非白人政府的诸多暴行，并宣称南非人民在非国大的领导下决不会妥协。另外，他还向那些打算采取联合抵制的方式制裁南非的国家表示谢意，但他坚持：“南非的民主和自由解放运动，其核心必定建立在南非的土地上。”
曼德拉用自己高超的演讲技巧和诚挚的感情为非国大和南非解放运动赢得了阵阵掌声。同时，在这次大会上，曼德拉还见证并参与了非洲统一组织的前期组织。当时，非洲各地区的关系颇为紧张，东非和中非民众不愿意接纳北非加入泛非自由运动组织。在曼德拉的斡旋之下，东非和中非领导作出了妥协，这让北非领导十分感激曼德拉。一年后，这个组织扩大到西非和北非，最终形成了非洲统一组织。
这之后，曼德拉先后走访了摩洛哥、塞内加尔、塞拉利昂等国，有的在口头上答应给予军事援助，有的则直接给予了经济支援——虽然只有5000美元左右。利比里亚的总统在为曼德拉提供了5000美元的援助之外，还偷偷塞给他400美元的路费，这让曼德拉十分感动。
6月，曼德拉回到了埃塞俄比亚，进行为期半年的军事训练，为领导民族之矛做准备。在这里，他学会了使用枪支、发射迫击炮、制作炸药等技能。同时，他还要接受军事理论方面的指导，这能帮他脱离政治人物的思维方式，学会像一个军事家那样去思考。
这次外出，曼德拉尽量低调，因为他知道南非政府并没有放过他，当他在英国访问时，就发现了很多南非当局的眼线。所以，当洛巴策的行政长官告诉曼德拉南非当局已经盯上他时，他便选择了立即返回南非。正好此时国内的斗争形势也十分严峻，政府通过《破坏运动法案》确立了“破坏分子稍有破坏行为，法院就有权判处死刑”的准则，南非黑人民众必须做好自卫的准备。而非国大和民族之矛也准备进行抗议，这些都需要曼德拉来主持大局。
但曼德拉不知道的是，等待他的是政府早已布下的天罗地网。