Nelson Mandela
hubungan dengan Partai Komunis, dan tidak memaksakan kekuasaan mayoritas. Mandela menolak semuanya dan menegaskan bahwa ANC hanya akan mengakhiri pemberontakan bersenjata jika pemerintah menghentikan kekerasan.
Ulang tahun Mandela ke-70 bulan Januari 1988 menarik perhatian internasional. BBC mengadakan konser musik Nelson Mandela 70th Birthday Tribute di Wembley Stadium, London. Meskipun dijadikan tokoh heroik di seluruh dunia, ia menghadapi masalah pribadi ketika para pemimpin ANC memberitahunya bahwa Winnie menjadi ketua geng penjahat, "Mandela United Football Club", yang bertanggung jawab atas penyiksaan dan pembunuhan
lawan-termasuk anak-anak-di Soweto. Walau banyak orang memaksa Mandela menceraikannya, ia tetap setia sampai Winnie dinyatakan bersalah oleh pengadilan.
Sepulihnya dari tuberkulosis yang disebabkan kondisi sel yang lembap, pada Desember 1988 Mandela dipindahkan ke Penjara Victor Verster dekat Paarl. Di sini, ia tinggal di rumah sipir yang lebih nyaman dengan koki pribadi; Mandela memanfaatkannya untuk menyelesaikan studi LLB-nya. Diizinkan banyak pengunjung, Mandela melakukan komunikasi rahasia dengan pemimpin ANC yang terasingkan, Oliver Tambo. Tahun
1989, Botha menderita stroke, tetap menjadi presiden tetapi mundur sebagai ketua Partai Nasional dan digantikan oleh F. W. de Klerk yang konservatif. Tanpa diduga, Botha mengundang Mandela minum teh pada Juli 1989; Mandela menyebutnya undangan yang hangat. Botha digantikan sebagai presiden oleh de Klerk enam minggu kemudian; presiden baru ini percaya bahwa apartheid tidak berkelanjutan dan membebaskan
semua tahanan ANC tanpa syarat kecuali Mandela. Setelah runtuhnya Tembok Berlin bulan November 1989, de Klerk memanggil kabinetnya untuk membicarakan legalisasi ANC dan pembebasan Mandela. Meski beberapa anggota kabinet sangat menentang renccananya, de Klerk bertemu Mandela pada Desember untuk mendiskusikan situasi ini, sebuah pertemuan yang dianggap bersahabat oleh kedua orang
tersebut, sebelum membebaskan Mandela tanpa syarat dan mengesahkan semua partai politik yang sebelumnya dibubarkan pada 2 Februari 1990.
Setelah keluar dari Victor Verster pada 11 Februari, Mandela menggandeng tangan Winnie di hadapan kerumunan dan pers; acara ini disiarkan langsung di seluruh dunia. Di Balai Kota Cape Town, ia menyampaikan pidato yang menyatakan komitmennya terhadap perdamaian dan rekonsiliasi dengan kaum minoritas kulit putih, tetapi menegaskan bahwa pemberontakan bersenjata ANC belum berakhir dan akan terus
berlanjut sebagai "aksi defensif murni terhadap kekejaman apartheid". Ia berharap pemerintah akan menyepakati negosiasi sehingga "pemberontakan bersenjata tidak diperlukan lagi" dan memaksa bahwa fokus utamanya adalah membawa perdamaian ke kalangan mayoritas kulit hitam dan memberi mereka hak suara di pemilu nasional dan lokal. Ketika tinggal di
rumah Desmond Tutu beberapa hari selanjutnya, Mandela bertemu teman-teman, aktivis, dan pers, dan berpidato di hadapan 100000 orang di Soccer City, Johannesburg.
Mandela melanjutkan tur Afrikanya, bertemu banyak pendukung dan politikus di Zambia, Zimbabwe, Namibia, Libya, dan Aljazair, kemudian ke Swedia untuk reuni dengan Tambo, lalu London, tempat ia tampil di konser di Wembley Stadium. Ketika mendorong negara-negara asing untuk mendukung sanksi terhadap pemerintah apartheid, di Perancis ia disambut Presiden François Mitterrand, di Kota Vatikan ia disambut Paus Yohanes Paulus II, dan di
Inggris ia bertemu Margaret Thatcher. Di Amerika Serikat, ia bertemu Presiden George H.W. Bush, berpidato di Kongres, dan berkunjung ke delapan kota; ia populer di kalangan masyarakat Afrika-Amerika. Di Kuba, ia bertemu Presiden Fidel Castro yang sudah lama digemarinya; keduanya bersahabat. Di Asia ia bertemu Presiden R. Venkataraman di India, Presiden Suharto di Indonesia dan Perdana Menteri Mahathir Mohamad di Malaysia, sebelum mengunjungi Australia dan Jepang. Ia justru tidak mengunjungi Uni Soviet, pendukung lama ANC.
Pada Mei 1990, Mandela memimpin delegasi multirasial ANC dalam negosiasi pendahuluan dengan delegasi 11 pria Afrikaner pemerintah. Mandela membuat mereka terkesan dengan diskusinya seputar sejarah Afrikaner, dan negosiasi ini berujung pada Groot Schuur Minute, yaitu pemeirntah mencabut keadaan darurat. Bulan Agustus, Mandela-mengakui kekurangan militer ANC yang sangat besar-menawarkan gencatan
senjata, Pretoria Minute, yang karena itulah ia dikritik habis-habisan oleh aktivis MK. Ia menghabiskan banyak waktu untuk menyatukan dan membangun ANC, tampil di konferensi Johannesburg bulan Desember yang dihadiri 1600 delegasi, kebanyakan menganggap Mandela lebih moderat daripada yang diharapkan. Pada konferensi nasional ANC Juli 1991 di Durban, Mandela mengakui kekurangan-kekurangan partai ini mengumumkan
rencananya untuk membangun "satuan tugas yang kuat dan kokoh" agar memperoleh kekuasaan mayoritas. Di konferensi tersebut, ia diangkat sebagai Presiden ANC, menggantikan Tambo yang sakit, dan eksekutif nasional multigender dan multiras dipilih bersama-sama.
Mandela diberikan kantor di markas ANC yang baru dibeli di Shell House, Johannesburg pusat, dan pindah bersama Winnie ke rumahnya yang besar di Soweto. Pernikahan mereka semakin renggang setelah ia tahu perselingkuhan Winnie dengan Dali Mpofu, tetapi ia mendukungnya saat Winnie diadili dengan tuduhan penculikan dan penyerangan. Ia mendapatkan dana untuk pembelaan Winnie dari International Defence and Aid dan
pemimpin Libya Muammar Gaddafi, namun pada Juni 1991 Winnie dinyatakan bersalah dan dihukum penjara enam tahun, dikurangi menjadi dua di pengadilan banding. Tanggal 13 April 1992, Mandela mengumumkan perpisahannya dengan Winnie, sedangkan ANC memaksa Winnie mengundurkan diri dari eksekutif nasional karena menyalahgunakan dana ANC; Mandela pindah ke pinggiran Johannesburg yang didominasi kulit putih, Houghton.
Reputasi Mandela semakin hancur akibat peningkatan kekerasan "hitam-ke-hitam", terutama antara pendukung ANC dan Inkatha di KwaZulu-Natal yang menewaskan ribuan orang. Mandela bertemu pemimpin Inkatha Buthelezi, tetapi ANC mencegah perundingan lebih lanjut mengenai masalah ini. Mandela mengakui bahwa ada "pasukan ketiga" di dalam dinas intelijen negara yang mengompori "pembantaian
rakyat" dan secara terbuka menyalahkan de Klerk-yang semakin tidak ia percayai-atas pembantaian Sebokeng. Pada bulan September 1991, konferensi perdamaian nasional diadakan di Johannesburg. Mandela, Buthelezi, dan de Klerk menandatangani perjanjian damai, tetapi kekerasan tetap berlanjut.
Convention for a Democratic South Africa (CODESA) diselenggarakan bulan Desember 1991 di Johannesburg World Trade Center, dihadiri oleh 228 delegasi dari 19 partai politik. Meski Cyril Ramaphosa memimpin delegasi ANC, Mandela masih menjadi tokoh penting, dan setelah de Klerk menggunakan pidato penutupnya untuk mengutuk kekerasan ANC, ia naik panggung dan menyebut de Klerk "pemimpin rezim minoritas yang tidak sah dan
terdiskreditkan". Karena didominasi Partai Nasional dan ANC, tidak banyak perundingan yang tercapai. CODESA 2 diadakan bulan Mei 1992. De Klerk memaksa Afrika Selatan pasca-apartheid harus memakai sistem federal dengan rotasi presiden untuk menjamin keselamatan etnis minoritas; Mandela menolaknya dan menuntut sistem kesatuan yang dikuasai kaum mayoritas. Setelah pembantaian Boipatong oleh
militan Inkatha yang dibantu pemerintah terhadap aktivis-aktivis ANC, Mandela membatalkan negosiasi tersebut sebelum menghadiri pertemuan Organisation of African Unity di Senegal. Di sana ia meminta agar Dewan Keamanan PBB mengadakan sidang istimewa dan pasukan penjaga perdamaian PBB diterjunkan di Afrika Selatan untuk mencegah "terorisme negara". PBB langsung mengirim utusan khusus Cyrus Vance ke negara ini untuk membantu
proses negosiasi. Menyerukan aksi massal dalam negeri, pada bulan Agustus ANC mengadakan mogok terbesar dalam sejarah Afrika Selatan dan para pendukungnya memadati jalanan Pretoria.