朋友的支持，友谊的帮助，对所有人来说都是巨大的动力来源，永远如此。只有那些准备好和朋友一起携手前进的人，才能够战胜巨大的困难。
——1998年7月1日曼德拉在领奖时的讲话
被释放后不久，为了争取国际社会的支持和认可，曼德拉代表非国大开始了为期半年左右的环球访问。他需要为非国大募集资金，并希望说服各国在南非的和谈没有正式结束前不要轻易放弃制裁。就他自己而言，他迫切希望了解这个世界，他已经落后于这个世界整整27年，他需要亲眼去见见这27年究竟发生了什么。
曼德拉先去赞比亚首都，会见了非国大的几位老朋友，赞比亚邻国的领袖也来了不少，他们都想见见心中的英雄。曼德拉和阿拉法特见了面，还一起交流了巴勒斯坦的解放问题。之后曼德拉访问了津巴布韦、纳米比亚等非洲国家。
随后曼德拉来到了非国大多年的盟友瑞典，他在那里接待了来自世界各地的访客，还见到了多年未见的老友奥利弗·塔柏。两位老人时隔30年终于再次见面，不禁紧紧相拥。奥利弗已经72岁，而且刚刚中风过，所以他希望曼德拉能代替自己担任非国大主席，但曼德拉觉得这样不妥，因为他才刚刚出狱，并不了解外面的状况。
几周后曼德拉来到了英国，这次撒切尔夫人没有安排和他会面，曼德拉也将注意力放在了感谢非国大在英国的伙伴上。英联邦秘书长为曼德拉举办了欢迎晚宴，曼德拉和温妮在晚宴上表现得像一对国王和王后，但这位“国王”十分谦卑，并在言语中一直强调自己的公仆身份。他还感谢了他们的支持，他说：“当我舒服地待在监狱里时，是你们冲在了最前线。”
1990年4月16日，曼德拉在英国著名的温布利体育场举办了一场大型音乐会，以答谢之前在他70岁生日时那些反隔离运动者为他举办的那场著名音乐会。这是一次音乐和政治的奇妙化学反应。由于英国政府依然对非国大持敌对态度，所以他们要求BBC不要报道非国大的宣传和筹款行为，最后搞得记者对台上偶像明星的一言一行都紧张兮兮的。这次演唱会盛况空前，无数明星免费参演，其中还包括曼德拉入狱前结识的曼哈顿兄弟组合。那天，共有7万多人来到了现场，共有10亿多观众在电视机前收看了这场演唱会。
之后，曼德拉短暂地回了一趟南非，拜祭了去世的母亲，之后便匆匆地踏上了去欧洲和北美的旅程。在法国，密特朗总统接待了他；在罗马，接待他的是教皇；在英国，曼德拉依然没有和撒切尔夫人见面，却通了一次愉快的电话。撒切尔夫人关心他的健康状况，并建议他减少行程。
曼德拉受到的最隆重的欢迎是在美国的纽约。在那里，人们把他当作《圣经》里的伟大摩西，成千上万的民众夹道欢迎他，无数欢迎彩带从摩天大厦上如雪花般飘落。到了晚上，非国大的3大代表色黑、绿和金黄色被用灯光打上了天空。这种场景连纽约州长都感到无比震撼。之后曼德拉在纽约黑人区的非洲广场发表了演说，他不卑不亢的演说方式和美国人经常见到的那种慷慨激昂的煽动性演说截然不同，这为他赢得了《纽约时报》的赞誉。
在华盛顿，布什总统会见了曼德拉。后来曼德拉还在美国参众两院的联席会议上发表了演讲，演讲之前，两院议员集体起立，进行了长达3分钟的鼓掌。曼德拉的演讲成功地打动了议员，他说服他们继续对南非进行制裁，直到南非的和谈结束。
这次美国之行给曼德拉带来了巨大的声誉，甚至是被神化。《时代周刊》把他形容成一个经典的英雄：“从坟墓中重生，充满创造力，完成了伟大的壮举。”并将他和玻利瓦尔、林肯等国家解放者相比。但曼德拉对此十分谦虚，他说：“我不是神，我只是一棵木桩，寄托着非国大所有的理想和渴望。”
之后，曼德拉先是访问了爱尔兰，然后再次来到英国。这次他终于和撒切尔夫人见了面。这次会面长达3个小时，双方都十分友好，他们对彼此的印象都很不错——虽然在立场上他们几乎是对立的。这次，撒切尔夫人也没有同意对南非进行制裁。
结束了对西方大国的访问后，曼德拉又来到了亚洲。印度、印度尼西亚、马来西亚等国都热情地接待了他，并给予了非国大资金支持。其中只有一站令曼德拉感到不满，那就是日本。当时日本有一位大臣曾发表过种族歧视言论，却依然掌握权柄，曼德拉对此感到震惊。同时，日本也没有答应曼德拉的募款请求。曼德拉后来说道：“日本政府做出的贡献几乎不值一提。”
相比对卡扎菲、萨达姆和阿拉法特等西方大国眼中钉的谨慎支持不同，曼德拉对古巴的卡斯特罗情有独钟。1991年曼德拉出访古巴时，受到了卡斯特罗的亲切接待，曼德拉称他为“相当有趣的家伙”。
虽然曼德拉有这么一帮不那么受西方待见的朋友，但这并未影响曼德拉在西方世界的受欢迎程度。虽然对曼德拉的欢迎和支持来得有点迟，但曼德拉依然感到十分欣慰。毕竟，一切都在向好的方向发展。
同时，冷静的曼德拉十分警惕众人对他的神化，虽然他知道这是非国大和他的一笔重要政治财富，但他不喜欢个人崇拜，他更享受作为一个平凡人的生活。他经常跟别人讲自己的糗事，比如被人索要签名，结果那人忘了曼德拉的名字。