شرع مانديلا في جولة أفريقية، التقى خلالها مشجعين وسياسيين في زامبيا وزيمبابوي وناميبيا وليبيا والجزائر، ثم انتقل إلى السويد حيث التقى بتامبو، وفي لندن، ظهر في حفل لـ «نيلسون مانديلا : منبر دولي من أجل الحرية في جنوب أفريقيا» في استاد ويمبلي.
شجع مانديلا الدول الأجنبية على دعم فرض عقوبات ضد حكومة الفصل العنصري. في فرنسا، استقبله الرئيس فرانسوا ميتران، وفي الفاتيكان البابا يوحنا بولس الثاني، والتقى في انجلترا بمارجريت تاتشر. حظي في الولايات المتحدة، باستقبال الرئيس جورج بوش الأب وألقى خطابا في مجلسي النواب والشيوخ وزار ثماني مدن أمريكية، وكان مانديلا يتمتع شعبية خاصة بين الأميركيين من أصول أفريقية. في كوبا، التقى بالرئيس فيدل كاسترو، الذي كان قدوته لفترة طويلة، وجمعت بين الاثنين صداقة.
في آسيا، قابل الرئيس ر. فينكاتارامان في الهند، والرئيس سوهارتو في إندونيسيا ورئيس الوزراء مهاتير محمد في ماليزيا، قبل زيارة أستراليا واليابان، والملاحظ أنه لم يقم بزيارة الاتحاد السوفياتي، الذي أيد حزب المؤتمر الوطني الأفريقي لفترة طويلة.
في مايو 1990، قاد مانديلا وفدا متعدد الأعراق من حزب المؤتمر الوطني الأفريقي في مفاوضات أولية مع وفد حكومي من 11 رجلا أفريكاني. أثار مانديلا أعجبهم عندما تحدث عن تاريخ الأفريكانية، توصلت المفاوضات إلى دقيقة “شور غروت”، التي خلالها قررت الحكومة رفع حالة الطوارئ. في أغسطس، عرض مانديلا - وهو مدرك لضرر العمل العسكري على حزب المؤتمر - وقفا لإطلاق النار. العرض جوبه بانتقادات واسعة من نشطاء MK.
ما دفع بمانديلا لقضاء الكثير من الوقت في محاولة لتوحيد وبناء حزب المؤتمر الوطني الأفريقي، ولدى ظهوره في مؤتمر جوهانسبرغ في ديسمبر والذي حضره 1600 مندوبا، وجده الكثير منهم أكثر اعتدالا مما كان متوقعا. في يوليو 1991، أثناء المؤتمر الوطني للحزب في ديربان، اعترف مانديلا بأخطاء الحزب وأعلن عن هدفه في بناء "فريق مهام قوي ومؤهل" لتأمين حكم الأغلبية. في المؤتمر، انتخب مانديلا رئيسا لحزب المؤتمر الوطني الأفريقي، ليحل محل تامبو المريض، كما تم انتخاب 50 عضوا تنفيذيا من أعراق وأجناس متعددة.
صار لمانديلا مكتب في المقر الجديد لحزب المؤتمر الوطني الأفريقي في شل هاوس، وسط جوهانسبرغ، في الوقت الذي انتقل مع ويني إلى منزلها الواسع بسويتو. توترت حياته الزوجية بشكل متزايد كلما ازداد دراية بعلاقة ويني بقضية «دالي مبوفو»، ولكنه وقف إلى جانبها طيلة فترة محاكمتها بتهم الخطف والاعتداء. حصل على تمويل للدفاع عنها من «الصندوق الدولي للدفاع والمعونة في جنوب أفريقيا» ومن الزعيم الليبي معمر القذافي.
ولكنها أدينت في يونيو 1991 وحكم عليها بالسجن لمدة ست سنوات، خفضت إلى اثنتين بعد الاستئناف. في 13 أبريل 1992، أعلن مانديلا على الملأ انفصاله عن ويني، في حين اضطرها حزب المؤتمر الوطني الأفريقي إلى التنحي من التنفيذي الوطني لاختلاس أموال حزب المؤتمر، وانتقلت مانديلا إلى ضاحية جوهانسبرغ ذات الغالبية البيضاء من هوتون لحقت أضرار بسمعة مانديلا بتزايد العنف بين السود، وخاصة بين حزب المؤتمر وأنصار انكاثا في كوازولو ناتال، سقط ضحيتها آلاف الموتى. التقى مانديلا بزعيم قبيلة بوتليزي، في حين منع حزب المؤتمر المزيد من المفاوضات بشأن هذه المسألة. اعترف مانديلا بوجود "قوة ثالثة" في أجهزة استخبارات الدولة تعمل على تأجيج "ذبح الشعب" وألقى باللوم صراحة على دي كليرك - الذي بدأ يفقد الثقة به بشكل متزايد - في مجزرة. Sebokeng في سبتمبر 1991، تم عقد مؤتمر للسلام الوطني في جوهانسبرج وقع خلاله كا من مانديلا وبوثيليزي ودي كليرك على اتفاق سلام، ورغم ذلك استمر العنف.