Nelson Mandela
Nelson Rolihlahla Mandela (; ) adalah seorang revolusioner antiapartheid dan politisi Afrika Selatan yang menjabat sebagai Presiden Afrika Selatan sejak 1994 sampai 1999. Ia adalah orang Afrika Selatan berkulit hitam pertama yang memegang jabatan tersebut dan presiden pertama yang terpilih melalui keterwakilan penuh, dalam sebuah pemilu multiras. Pemerintahannya berfokus pada penghapusan pengaruh apartheid dengan memberantas rasisme, kemiskinan dan kesenjangan, dan mendorong rekonsiliasi rasial. Selaku nasionalis Afrika dan sosialis demokratik, ia menjabat sebagai Presiden Kongres Nasional Afrika (ANC) pada 1991 sampai 1997. Selain itu, Mandela pernah menjadi Sekretaris Jenderal Gerakan Non-Blok pada 1998 sampai 1999.
Terlahir dari keluarga kerajaan Thembu dan bersuku Xhosa, Mandela belajar hukum di Fort Hare University dan University of Witwatersrand. Ketika menetap di Johannesburg, ia terlibat dalam politik antikolonial, bergabung dengan ANC, dan menjadi anggota pendiri Liga Pemuda ANC. Setelah kaum nasionalis Afrikaner dari Partai Nasional berkuasa tahun 1948 dan menerapkan kebijakan apartheid, popularitas Mandela melejit di Defiance Campaign ANC tahun 1952, terpilih menjadi Presiden ANC Transvaal, dan menghadiri Congress of the People tahun 1955. Sebagai pengacara, ia berulang kali ditahan karena melakukan aktivitas menghasut dan, sebagai ketua ANC, diadili di Pengadilan Pengkhianatan pada 1956 sampai 1961, namun akhirnya divonis tidak bersalah. Meski awalnya berunjuk rasa tanpa kekerasan, ia dan Partai Komunis Afrika Selatan mendirikan militan Umkhonto we Sizwe (MK) tahun 1961 dan memimpin kampanye pengeboman terhadap target-target pemerintahan. Pada 1962, ia ditahan dan dituduh melakukan sabotase dan bersekongkol menggulingkan pemerintahan, dan dihukum penjara seumur hidup di Pengadilan Rivonia.
Mandela menjalani masa kurungan 27 tahun, pertama di Pulau Robben, kemudian di Penjara Pollsmoor dan Penjara Victor Verster. Kampanye internasional yang menuntut pembebasannya membuat Mandela dibebaskan tahun 1990. Setelah menjadi Presiden ANC, Mandela menerbitkan otobiografi dan bernegosiasi dengan Presiden F.W. de Klerk untuk menghapuskan apartheid dan melaksanakan pemilu multiras tahun 1994 yang kelak dimenangkan ANC. Ia terpilih sebagai Presiden dan membentuk Pemerintahan Persatuan Nasional. Selaku Presiden, ia menyusun konstitusi baru dan membentuk Komisi Kebenaran dan Rekonsiliasi untuk menyelidiki pelanggaran-pelanggaran HAM sebelumnya. Ia juga memperkenalkan kebijakan reformasi lahan, pemberantasan kemiskinan, dan perluasan cakupan layanan kesehatan. Di luar negeri, ia bertindak sebagai mediator antara Libya dan Britania Raya dalam pengadilan pengeboman Pan Am Penerbangan 103 dan mengawasi intervensi militer di Lesotho. Ia menolak mencalonkan diri untuk kedua kalinya dan digantikan oleh wakilnya, Thabo Mbeki. Ia kemudian menjadi negarawan ulung yang berfokus pada aktivitas amal demi memberantas kemiskinan dan HIV/AIDS melalui Nelson Mandela Foundation.
Kontroversial nyaris sepanjang hayatnya, para kritikus sayap kanan menyebut Mandela teroris dan simpatisan komunis. Meski begitu, ia memperoleh pengakuan internasional atas sikap antikolonial dan antiapartheidnya, menerima lebih dari 250 penghargaan, termasuk Hadiah Perdamaian Nobel 1993, Medali Kebebasan Presiden Amerika Serikat, dan Order of Lenin dari Uni Soviet. Ia sangat dihormati di Afrika Selatan dan lebih dikenal dengan nama klan Xhosa-nya, Madiba atau tata. Nelson Mandela sering dijuluki "bapak bangsa".
Mandela lahir tanggal 18 Juli 1918 di desa Mvezo di Umtatu, waktu itu terletak di Provinsi Cape, Afrika Selatan. Dengan nama depan Rolihlahla, istilah Xhosa yang berarti "pembuat masalah", ia nantinya justru lebih dikenal dengan nama klannya, Madiba. Kakek buyut dari ayahnya, Ngubengcuka, adalah penguasa suku Thembu di Teritori Transkei yang saat ini menjadi provinsi Eastern Cape di Afrika Selatan. Salah satu putranya, "Mandela", menjadi kakek Nelson dan sumber nama belakangnya. Karena Mandela adalah satu-satunya putra raja yang ibunya berasal dari klan Ixhiba, "Dinasti Tangan Kiri", keturunan cabang kadet keluarga kerajaannya bersifat morganatik, artinya tidak berhak mewarisi takhta tetapi diakui sebagai anggota dewan kerajaan yang jabatannya turun temurun. Karena itu, ayahnya, Gadla Henry Mphakanyiswa, merupakan kepala suku setempat dan anggota dewan kerajaan; ia dilantik tahun 1915 setelah pendahulunya dituduh korupsi oleh hakim kulit putih yang berkuasa waktu itu. Pada tahun 1926, Gadla juga dituduh melakukan korupsi dan Nelson kelak diberitahu bahwa ayahnya dipecat karena bersikukuh menolak permintaan hakim yang tidak masuk akal. Sebagai penyembah dewa Qamata, Gadla adalah seorang poligamis yang memiliki empat istri, empat putra, dan sembilan putri, yang tinggal di beberapa desa. Ibu Nelson, Nosekeni Fanny, adalah istri ketiga Gadla yang merupakan putri Nkedama dari Dinasti Tangan Kanan dan anggota klan amaMpemvu.
Sempat menyebut kehidupan awalnya didominasi "adat, ritual, dan tabu", Mandela tumbuh bersama dua saudarinya di "kraal" ibunya di desa Qunu, tempat Mandela bekerja sebagai gembala sapi dan menghabiskan waktunya bersama anak-anak lain. Kedua orang tuanya buta huruf, namun merupakan penganut Kristen yang taat. Ibunya mengirimkan Mandela ke sekolah Methodis setempat ketika menginjak usia 7 tahun. Dibaptis sebagai Methodis, Mandela diberi nama depan Inggris "Nelson" oleh gurunya. Saat Mandela kira-kira berusia 9 tahun, ayahnya menetap di Qunu dan meninggal akibat penyakit yang tidak diketahui yang diyakini Mandela sebagai penyakit paru-paru. Merasa "terabaikan", ia kelak mengaku mewarisi "sifat pemberontak bangga" dan "rasa keadilan yang keras" dari ayahnya.
Ibunya membawa Mandela ke istana "Great Place" di Mqhekezweni, lalu dipercayakan untuk asuhan bupati Thembu, Kepala Suku Jongintaba Dalindyebo. Meski ia tidak akan melihat ibunya lagi selama sekian tahun, Mandela merasa bahwa Jongintaba dan istrinya Noengland memperlakukannya seperti anak sendiri, membesarkannya bersama putra-putri mereka, Justice dan Nomafu. Karena Mandela sering menghadiri misa setiap Minggu bersama orang tua asuhnya, Kristen menjadi bagian utama hidupnya. Ia mengenyam pendidikan di sekolah misi Methodis dekat istana tersebut. Di sana ia belajar bahasa Inggris, Xhosa, sejarah, dan geografi. Ia mulai tertarik dengan sejarah Afrika, mendengarkan cerita-cerita yang diujarkan para pengunjung istana yang tua, dan terpengaruh retorika antiimperialis Kepala Suku Joyi. Waktu itu, ia tetap saja menganggap kolonialis Eropa sebagai penolong, bukan penindas. Pada usia 16 tahun, ia, Justice, dan teman-temannya berangkat ke Tyhalarha untuk menjalani ritual sunat yang secara simbolis menandakan mereka sudah dewasa. Seusai ritual, Mandela diberi nama "Dalibunga".
Untuk mendapatkan keterampilan supaya bisa menjadi anggota dewan penasihat untuk keluarga raja Thembu, Mandela mengenyam pendidikan menengah di Clarkebury Boarding Institute di Engcobo, institusi bergaya Barat yang merupakan sekolah Afrika berkulit hitam terbesar di Thembuland. Dirancang supaya murid-muridnya saling bersosialisasi setiap hari, ia mengklaim kehilangan sikap "tertutupnya" dan berteman baik dengan wanita untuk pertama kalinya; ia mulai berolahraga dan merintis kecintaannya dalam berkebun. Setelah menyelesaikan Junior Certificate selama dua tahun, pada tahun 1937 ia pindah ke Healdtown, perguruan Methodis di Fort Beaufort yang juga dihadiri sebagian besar anggota keluarga raja Thembu, termasuk Justice. Kepala sekolah menekankan superioritas budaya dan pemerintahan Inggris, namun Mandela semakin tertarik dengan budaya Afrika pribumi dan berteman untuk pertama kalinya dengan orang non-Xhosa, seorang penutur bahasa Sotho, dan dipengaruhi salah satu guru favoritnya, seorang Xhosa yang mematahkan tabu dengan menikahi orang Sotho. Selain menghabiskan waktu luangnya dengan berlari dan tinju, pada tahun keduanya Mandela memutuskan menjadi prefek.
Dengan bantuan Jongintaba, Mandela mengambil gelar Bachelor of Arts (BA) di University of Fort Hare, institusi kulit hitam elit di Alice, Eastern Cape dengan kurang lebih 150 mahasiswa. Di sana ia belajar bahasa Inggris, antropologi, politik, pemerintahan pribumi, dan hukum Belanda Romawi pada tahun pertamanya, dan ingin menjadi penerjemah atau juru tulis di Departemen Urusan Pribumi. Mandela menetap di asrama Wesley House, berteman dengan Oliver Tambo dan sesama anggota sukunya, K.D. Matanzima. Melanjutkan ketertarikannya di bidang olahraga, Mandela mengambil kelas tari ballroom, dan terlibat dalam pementasan drama tentang Abraham Lincoln. Sebagai anggota Students Christian Association, ia memimpin kelas Injil untuk masyarakat setempat dan menjadi pendukung Britania Raya ketika Perang Dunia Kedua pecah. Meski teman-temannya memiliki hubungan dengan Kongres Nasional Afrika (ANC) dan gerakan antiimpterialis, Mandela tidak mau terlibat. Setelah membantu mendirikan House Committee untuk mahasiswa tahun pertama yang melawan dominasi mahasiswa tahun kedua, di akhir tahun pertamanya ia terlibat aksi boikot Students' Representative Council (SRC) terhadap kualitas makanan, sehingga ia diskors sementara dari universitas; ia meninggalkan kuliahnya tanpa gelar.
Sepulangnya ke Mqhekezweni bulan Desember 1940, Mandela mengetahui bahwa Jongintaba telah mengatur dua pernikahan untuk Mandela dan Justice; karena tidak senang, mereka pergi ke Johannesburg melalui Queenstown dan tiba bulan April 1941. Mandela bekerja sebagai pengawas malam di Crown Mines, "pemandangan kapitalisme Afrika Selatan pertama[nya]", tetapi dipecat setelah "induna" (mandor) mengetahui ia kabur dari rumah. Setelah menetap di rumah sepupunya di Kotapraja George Goch, Mandela diperkenalkan pada pemasar rumah dan aktivis ANC Walter Sisulu, yang memberinya pekerjaan sebagai "articled clerk" di firma hukum Witkin, Sidelsky and Edelman. Perusahaan ini dioperasikan oleh seorang Yahudi liberal, Lazar Sidelsky, yang simpati terhadap perjuangan ANC. Di firma tersebut, Mandela berteman dengan Gaur Redebe, anggota ANC dan Partai Komunis bersuku Xhosa, dan Nat Bregman, komunis Yahudi yang menjadi teman kulit putih pertamanya. Dengan menghadiri pertemuan-pertemuan komunis, Mandela terpesona melihat orang Eropa, Afrika, India dan Kleurlinge berbaur begitu saja. Akan tetapi, ia kemudian mengaku tidak bergabung dengan Partai tersebut karena sifat ateismenya bertentangan dengan keyakinan Kristen Mandela, dan karena ia memandang perjuangan Afrika Selatan lebih berbasis ras alih-alih kesejahteraan kelas. Semakin terpolitisasi, bulan Agustus 1943 Mandela mendukung boikot bus demi menggagalkan kenaikan tarif. Untuk melanjutkan pendidikan tingginya, Mandela mengikuti kursus korespondensi di University of South Africa dan mengerjakan tugas akhirnya pada malam hari.
Dengan upah kecil, Mandela menyewa kamar di rumah keluarga Xhoma di Kotapraja Alexandra; meski penuh kemiskinan, kejahatan, dan polusi, Alexandra selalu menjadi "tempat berharga" baginya. Walaupun malu dengan kemiskinan yang dialaminya, ia sempat merayu seorang wanita Swazi sebelum gagal merayu putri tuan tanahnya. Setelah menemukan kamar sewa yang lebih murah, Mandela pindah ke markas Witwatersrand Native Labour Association, tinggal bersama para penambang dari berbagai suku dan bertemu Ratu Basutoland. Pada akhir 1941, Jongintaba mengunjungi Mandela dan memaafkan kelakuannya. Sepulangnya ke Thembuland, sang bupati meninggal dunia pada musim dingin 1942, Mandela dan Justice terlambat sehari untuk menghadiri pemakamannya. Pasca wisuda awal 1943, Mandela kembali ke Johannesburg untuk menjadi pengacara alih-alih anggota dewan penasihat di Thembuland. Ia kelak berkata bahwa saat itu ia tidak sadar, tapi "mengetahui diriku sedang melakukannya dan tidak bisa melawan."
Saat belajar hukum di University of Witwatersrand, Mandela adalah satu-satunya orang pribumi Afrika di fakultas tersebut, dan meski menghadapi rasisme ia berteman dengan sejumlah mahasiswa Eropa, Yahudi, dan India liberal dan komunis, termasuk Joe Slovo, Harry Schwarz, dan Ruth First. Setelah bergabung dengan ANC, Mandela semakin dipengaruhi Sisulu dan menghabiskan waktunya bersama aktivis lain di rumah Sisulu di Orlando, termasuk teman lamanya Oliver Tambo. Tahun 1943, Mandela bertemu Anton Lembede, seorang nasionalis Afrika yang sangat menentang front ras bersatu terhadap kolonialisme dan imperialisme atau aliansi dengan kaum komunis. Meski berteman dengan orang non-kulit hitam dan komunis, Mandela mendukung pandangan Lembede, percaya bahwa orang Afrika kulit hitam harus terbebas sepenuhnya dalam perjuangan mendapatkan penentuan nasib sendiri secara politik. Merasa perlunya sayap pemuda untuk memobilisasi penduduk Afrika secara besar-besaran dalam penentangan penindasan mereka, Mandela ikut dalam delegasi yang memberitahu Presiden ANC Alfred Bitini Xuma soal rencana tersebut dirumahnya di Sophiatown; African National Congress Youth League (ANCYL) didirikan pada Minggu Paskah 1944 di Bantu Men's Social Centre di Eloff Street; Lembede menjadi Presiden dan Mandela menjadi anggota komite eksekutif.
Di rumah Sisulu, Mandela bertemu Evelyn Mase, seorang aktivis ANC dan perawat dari Engcobo, Transkei. Menikah tanggal 5 Oktober 1944, setelah awalnya tinggal bersama kerabat Evelyn, mereka menyewa Rumah no. 8115 di Orlando pada awal 1946. Anak pertama mereka, Madiba "Thembi" Thembekile, lahir bulan Februari 1946, sementara seorang putri bernama Makaziwe lahir tahun 1947 namun meninggal 9 bulan kemudian akibat meningitis. Mandela menikmati kehidupan rumah tangga, mengajak ibu dan saudarinya Leabie untuk tinggal bersamanya. Pada awal 1947, masa kerjanya di Witkin, Sidelsky and Edelman selama tiga tahun berakhir dan ia memutuskan menjadi mahasiswa purnawaktu, bergantung pada pinjaman dari Bantu Welfare Trust.
Bulan Juli 1947, Mandela melarikan Lembede ke rumah sakit, tempat ia meninggal dunia; Lembede digantikan sebagai presiden ANCYL oleh Peter Mda yang lebih moderat dan sepakat bekerja sama dengan kaum komunis dan non-kulit hitam. Mda menunjuk Mandela sebagai sekretaris ANCYL. Pada Desember 1947, Mandela tidak sependapat dengan pendekatan Mda untuk mendukung upaya pengusiran kaum komunis dari ANCYL, karena ideologi mereka dianggap tidak Afrikawi; upaya ini terbukti gagal. Tahun 1947, Mandela terpilih masuk komite eksekutif ANC Transvaal di bawah presiden regional C.S. Ramohanoe. Ketika Ramohanoe bertindak melawan keinginan Komite Eksekutif Transvaal dengan bekerja sama dengan orang India dan komunis, Mandela termasuk salah satu yang memaksanya mengundurkan diri.
Pada pemilihan umum Afrika Selatan 1948 yang hanya boleh diikuti penduduk kulit putih, Partai Herenigde Nasionale yang didominasi Afrikaner pimpinan Daniel François Malan menang dan bergabung dengan Partai Afrikaner menjadi Partai Nasional. Karena rasialis secara terbuka, partai ini meresmikan dan memperluas segregasi ras melalui undang-undang apartheid yang baru. Semakin meningkat pengaruhnya di ANC, Mandela dan kader-kadernya mulai menyerukan aksi langsung terhadap apartheid, seperti boikot dan mogok, yang dipengaruhi oleh taktik masyarakat India Afrika Selatan. Xuma tidak mendukung aksi ini dan didepak dari kursi presiden melalui pemungutan suara tidak percaya dan digantikan oleh James Moroka dan kabinet yang lebih militan yang terdiri dari Sisulu, Mda, Tambo, dan Godfrey Pitje; Mandela kelak berkata bahwa "Kami sekarang telah memandu ANC ke jalur yang lebih radikal dan revolusioner." Karena meluangkan waktunya untuk politik, Mandela gagal pada tahun terakhirnya sebanyak tiga kali di Witwatersrand; gelarnya akhirnya ditahan permanen pada Desember 1949.
Mandela menggantikan Xuma sebagai Eksekutif Nasional ANC pada bulan Maret 1950. Bulan itu, Defend Free Speech Convention diadakan di Johannesburg dan meminta para aktivis Afrika, India, dan komunis melakukan mogok massal antiapartheid. Mandela menentang mogok tersebut karena tidak dipimpin ANC, tetapi mayoritas pekerja berkulit hitam terlibat, sehingga kepolisian terpaksa meningkatkan aksi kekerasan dan memperkenalkan Undang-Undang Pemberantasan Komunisme 1950 yang memengaruhi aksi semua kelompok pengunjuk rasa. Pada tahun 1950, Mandela terpilih sebagai presiden nasional ANCYL; di konferensi nasional ANC Desember 1951, ia terus menentang front ras bersatu, sayangnya ia kalah jumlah suara. Sejak itu, ia mengubah seluruh sudut pandangnya dan beralih ke pandangan tadi; dipengaruhi teman-temannya seperti Moses Kotane dan dukungan Uni Soviet terhadap perang pembebasan nasional. Ketidakpercayaan Mandela terhadap komunisme juga patah. Ia terpengaruh tulisan-tulisan Karl Marx, Friedrich Engels, Vladimir Lenin, Joseph Stalin, dan Mao Zedong, dan menganut materialisme dialektik. Pada April 1952, Mandela mulai bekerja di firma hukum H.M. Basner, meski komitmen kerja dan aktivismenya yang meningkat berarti ia menghabiskan lebih sedikit waktunya untuk keluarga.
Tahun 1952, ANC memulai persiapan Defiance Campaign gabungan terhadap apartheid dengan kelompok India dan komunis dan mendirikan National Voluntary Board untuk merekrut voluntir. Tentang jalur pemberontakan non-kekerasan yang dipengaruhi Mohandas Gandhi, beberapa pihak menganggapnya pilihan yang etis, tetapi Mandela menganggapnya pragmatis. Di rapat umum Durban tanggal 22 Juni, Mandela menyampaikan pidato di hadapan 10.000 orang, memulai protes kampanye, yang karena itu ia ditangkap dan ditahan sementara di penjara Marshall Square. Seiring berlanjutnya protes, keanggotaan ANC meledak dari 20.000 menjadi 100.000; pemerintah menanggapi dengan penangkapan massal dan memperkenalkan Undang-Undang Keselamatan Umum 1953 supaya bisa menerapkan darurat militer. Bulan Mei, pihak berwenang melarang Presiden ANU Transvaal J. B. Marks tampil di hadapan publik; karena gagal mempertahankan posisinya, ia menyarankan agar Mandela menggantikannya. Meski kelompok ultra-Afrikanis Bafabegiya menentang pencalonannya, Mandela terpilih sebagai presiden regional pada bulan Oktober.
Tanggal 30 Juli 1952, Mandela ditangkap di bawah UU Pemberantasan Komunisme dan diadili sebagai bagian dari 21 orang terdakwa—termasuk Moroka, Sisulu, dan Dadoo—di Johannesburg. Dinyatakan bersalah karena "komunisme menurut undang-undang", hukuman kerja paksa mereka selama sembilan bulan diperpanjang menjadi dua tahun. Bulan Desember, Mandela dijatuhkan larangan menghadiri pertemuan atau berbicara kepada lebih dari satu orang dalam satu waktu selama enam bulan, sehingga kepresidenan ANU Transvaal-nya menjadi tidak praktis. Defiance Campaign berangsur-angsur selesai. Bulan September 1953, Andrew Kunene membacakan pidato "No Easy Walk to Freedom" Mandela di sebuah pertemuan ANC Transvaal; judulnya diambil dari kutipan pemimpin kemerdekaan India Jawaharlal Nehru, kelak memengaruhi pemikiran Mandela. Pidato ini menetapkan rencana cadangan seandainya ANC dibubarkan. Rencana Mandela ("Mandela Plan") atau M-Plan ini terdiri dari pembelahan organisasi menjadi struktur sel dengan kepemimpinan yang lebih tersentralisasi.
Mandela mendapatkan pekerjaan sebagai pengacara untuk firma Terblanche and Briggish sebelum pindah ke Helman and Michel yang liberal dan lulus tes kualifikasi untuk menjadi pengacara penuh. Pada Agustus 1953, Mandela dan Oliver Tambo membuka firma hukumnya sendiri, Mandela and Tambo, yang beroperasi di pusat kota Johannesburg. Sebagai satu-satunya firma hukum milik orang Afrika di negara itu, firma ini populer di kalangan orang kulit hitam yang merasa dirugikan dan sering menangani kasus kebrutalan polisi. Karena tidak disukai pihak berwenang, firma ini dipaksa pindah ke lokasi terpencil setelah izin pendiriannya dicabut sesuai Group Areas Act; akibatnya, pengguna jasa mereka menyusut. Walau putri kedua, Makaziwe Phumia, lahir pada Mei 1954, hubungan Mandela dengan Evelyn merenggang dan Evelyn menuduhnya selingkuh. Bukti-bukti muncul bahwa ia selingkuh dengan anggota ANC Lillian Ngoyi dan sekretaris Ruth Mompati; klaim kuat namun tanpa bukti menandakan Mompati memiliki anak dengan Mandela. Karena jijik akan kelakuan putranya, Nosekeni pulang ke Transkei, sedangkan Evelyn memeluk Saksi-Saksi Yehuwa dan menentang obsesi politik Mandela.
Mandela berpendapat bahwa ANC "tidak punya alternatif terhadap pemberontakan bersenjata dan keras" setelah terlibat dalam unjuk rasa yang gagal mencegah penggusuran kota pinggiran berpenduduk kulit hitam Sophiatown, Johannesburg, pada Februari 1955. Ia menyarankan Sisulu agar meminta persenjataan dari Republik Rakyat Tiongkok, tetapi meski mendukung perjuangan antiapartheid, pemerintah Tiongkok percaya gerakan ini tidak cukup siap untuk perang gerilya. Dengan keterlibatan South African Indian Congress, Coloured People's Congress, South African Congress of Trade Unions dan Congress of Democrats, ANC berencana mengadakan Kongres Rakyat, meminta semua warga Afrika Selatan mengirimkan proposal untuk zaman pasca-apartheid. Berdasarkan tanggapan-tanggapan ini, Piagam Kebebasan dirancang oleh Rusty Bernstein yang isinya meminta pembentukan negara demokratis non-rasialis disertai nasionalisasi industri besar. Saat piagam ini diadopsi pada konferensi Juni 1955 di Kliptown yang dihadiri 3000 delegasi, polisi membubarkan acara, namun ini tetap menjadi bagian utama ideologi Mandela.
Setelah akhir pelarangan kedua bulan September 1955, Mandela cuti kerja ke Transkei untuk membahas dampak Undang-Undang Otoritas Bantu 1951 bersama ketua-ketua suku setempat. Ia juga menjenguk ibunya dan Noengland sebelum melanjutkan perjalanan ke Cape Town. Pada Maret 1956, ia dijatuhkan larangan tampil di hadapan publik untuk ketiga kalinya, melarangnya masuk Johannesburg selama lima tahun, tetapi sering ia langgar. Pernikahannya berakhir setelah Evelyn meninggalkan Mandela, membawa anak-anak mereka ke rumah saudaranya. Saat memulai sidang cerai bulan Mei 1956, ia mengklaim Mandela menyiksanya secara fisik; ia menolak tuduhan-tuduhan tersebut dan berjuang mendapatkan hak asuh anak-anaknya. Evelyn menarik petisi perceraiannya pada November, namun Mandela meminta cerai pada Januari 1958; perceraian ini akhirnya diputuskan bulan Maret yang hasilnya anak-anak berada di bawah asuhan Evelyn. Selama sidang cerai, Mandela mulai merayu dan melakukan politisasi terhadap seorang pekerja sosial, Winnie Madikizela, yang ia nikahi di Bizana tanggal 14 Juni 1958. Madikizela kelak terlibat dalam aktivitas ANC dan sempat dipenjara selama beberapa minggu.
Pada tanggal 5 Desember 1956, Mandeal ditahan bersama sebagian besar eksekutif ANC karena "pengkhianatan tinggi" terhadap negara. Pada sidang di Penjara Johannesburg yang dipenuhi unjuk rasa massal, mereka menjalani pemeriksaan sementara di Drill Hall tanggal 19 Desember sebelum dibebaskan dengan jaminan. Sidang sanggahan terdakwa dimulai tanggal 9 Januari 1957, melibatkan pengacara terdakwa Vernon Berrangé, dan berlanjut sampai ditangguhkan pada bulan September. Pada Januari 1958, hakim Oswald Pirow ditunjuk untuk menangani kasus ini, dan pada Februari ia memutuskan bahwa ada "bukti yang cukup" supaya para terdakwa diadili di Mahkamah Agung Transvaal. Pengadilan Pengkhianatan resmi dimulai di Pretoria bulan Agustus 1958 dan para terdakwa berhasil meminta ketiga hakim—semuanya terlibat dengan Partai Nasional yang berkuasa—diganti. Pada Agustus, satu tuduhan dicabut, dan pada Oktober jaksa menarik dakwaannya dan mengirim rancangan baru pada November yang berpendapat bahwa pemimpin ANC melakukan pengkhianatan tinggi dengan menyerukan revolusi kekerasan, tuduhan yang ditolak mentah-mentah oleh terdakwa.
Pada April 1959, para militan Afrikanis yang tidak puas dengan pendekatan front bersatu ANC mendirikan Pan-African Congress (PAC); teman Mandela Robert Sobukwe terpilih menjadi presiden, meski Mandela menganggap kelompok ini "tidak dewasa". Kedua partai menyerukan kampanye antipas pada bulan Mei 1960, yaitu pembakaran pas yang wajib dibawa ke mana-mana oleh penduduk Afrika. Salah satu demonstrasi PAc dibubarkan polisi dan menewaskan 69 pengunjuk rasa dalam pembantaian Sharpeville. Sebagai bentuk solidaritas, Mandela membakar pasnya ketika kerusuhan pecah di seluruh Afrika Selatan, sehingga pemerintah memberlakukan darurat militer. Di bawah kondisi Keadaan Darurat, Mandela dan sejumlah aktivis lain ditangkap pada tanggal 30 Maret, dipenjara tanpa tuduhan di penjara lokal Pretoria yang kotor, sementara ANC dan PAC dibubarkan pada bulan April. Hal ini membuat para pengacaranya sulit menghubungi mereka dan disepakati bahwa tim terdakwa untuk Pengadilan Pengkhianatan harus mengundurkan diri sebagai bentuk protes. Mewakili mereka di pengadilan, para terdakwa dibebaskan dari penjara ketika keadaan darurat dicabut pada akhir Agustus. Mandela memanfaatkan waktu luangnya untuk mengadakan All-In African Conference dekat Pietermaritzburg, Natal, pada bulan Maret yang dihadiri 1.400 delegasi antiapartheid dan menyepakati protes mogok kerja untuk memperingati 31 Mei, hari ketika Afrika Selatan menjadi negara republik. Tanggal 29 Maret 1961, setelah pengadilan berlangsung selama enam tahun, para hakim menjatuhkan vonis tidak bersalah yang lantas mempermalukan pemerintah.
Menyamar sebagai sopir, Mandela berkeliling Afrika Selatan secara rahasia dan menyusun struktur sel baru ANC dan mogok kerja massal pada 29 Mei. Dijuluki "Black Pimpernel" di media—mengutip novel Emma Orczy tahun 1905 "The Scarlet Pimpernel"—polisi mengeluarkan surat perintah penangkapannya. Mandela mengadakan beberapa rapat rahasia dengan wartawan, dan setelah pemerintah gagal mencegah mogok tersebut, ia memperingatkan mereka bahwa banyak aktivis antiapartheid yang beralih ke aksi kekerasan melalui kelompok-kelompok seperti Poqo PAC. Ia yakin bahwa ANC harus membentuk kelompok bersenjata untuk menyalurkan aksi-aksi kekerasannya dan meyakinkan ketua ANC Albert Luthuli—yang secara moral menentang kekerasan—dan kelompok aktivis sekutu tentang perlunya hal tersebut.
Terinspirasi oleh Gerakan 26 Juli Fidel Castro dalam Revolusi Kuba, pada tahun 1961 Mandela ikut mendirikan Umkhonto we Sizwe ("Tombak Bangsa", disingkat "MK") bersama Sisulu dan komunis Joe Slovo. Ketika menjabat sebagai ketua grup militan ini, ia mendapatkan sejumlah ide dari literatur ilegal tentang perang gerilya karya Mao dan Che Guevara. Setelah terpisah secara resmi dari ANC, pada tahun-tahun berikutnya MK menjadi sayap bersenjata dari grup tersebut. Kebanyakan anggota awal MK adalah komunis berkulit putih; setelah bersembunyi di flat Wolfie Kodesh di Berea, Mandela pindah ke Liliesleaf Farm milik komunis di Rivonia dan bergabung dengan Raymond Mhlaba, Slovo, dan Bernstein, yang sama-sama menyusun konstitusi MK. Beroperasi dengan struktur sel, MK sepakat melakukan sabotase demi memberi tekanan besar terhadap pemerintah dengan korban kecil, mengebom instalasi militer, pembangkit listrik, kabel telepon, dan jalur transportasi pada malam hari ketika tidak ada warga sipil. Mandela mencatat bahwa jika taktik-taktik tersebut gagal, MK akan beralih ke "peperangan gerilya dan terorisme." Sesaat setelah pemimpin ANC Luthuli mendapatkan Hadiah Perdamaian Nobel, MK mengumumkan keberadaan mereka ke publik dan rencana 57 pengeboman pada Hari Dingane (16 Desember) 1961, diikuti serangan-serangan lain pada Malam Tahun Baru.
ANC setuju mengirim Mandela sebagai perwakilan mereka di pertemuan Pan-African Freedom Movement for East, Central and Southern Africa (PAFMECSA) Addis Ababa, Ethiopia, Februari 1962. Bepergian secara rahasia, Mandela bertemu Kaisar Haile Selassie I dan berpidato setelah pidato Selassie di konferensi tersebut. Pasca konferensi, ia mengunjungi Kairo, Mesir, menyukai reformasi politik Presiden Gamal Abdel Nasser, dan pergi ke Tunis, Tunisia, tempat Presiden Habib Bourguiba memberinya dana £5000 untuk persenjataan. Ia kemudian melanjutkan perjalanan ke Maroko, Mali, Guinea, Sierra Leone, Liberia, dan Senegal, sambil menerima bantuan dana dari Presiden Liberia William Tubman dan Presiden Guinea Ahmed Sékou Touré. Di London, Inggris, ia bertemu para aktivis antiapartheid, wartawan, dan politikus kiri ternama. Di Ethiopia, ia mengikuti kursus perang gerilya selama enam bulan, namun hanya sempat menyelesaikan dua bulan saja sebelum dipanggil pulang ke Afrika Selatan.
Pada 5 Agustus 1962, polisi menangkap Mandela dan Cecil Williams dekat Howick. Ditahan di penjara Marshall Square, Johannesburg, ia dituduh menghasut mogok buruh dan ke luar negeri tanpa izin. Mewakili dirinya sendiri ditemani Slovo sebagai penasihat hukum, Mandela hendak memanfaatkan pengadilan ini untuk menunjukkan "penentangan moral ANC terhadap rasisme" sementara para pendukungnya berdemo di luar pengadilan. Setelah dipindahkan ke Pretoria, tempat yang bisa dijangkau Winnie, Mandela mulai mengambil studi korespondensi untuk mendapatkan gelar Bachelor of Laws (LLB) dari University of London dari dalam selnya. Sidang dengar pendapatnya dimulai tanggal 15 Oktober, tetapi ia mengganggu jalannya sidang dengan mengenakan "kaross" tradisional, menolak memanggil saksi mata, dan mengganti permohonan keringanannya menjadi pidato politik. Dinyatakan bersalah, Mandela dihukum penjara lima tahun; ketika ia keluar dari ruang sidang, para pendukungnya menyanyikan "Nkosi Sikelel iAfrika".
Tanggal 11 Juli 1963, polisi menggeledah Lilielsleaf Farm, menahan semua orang di sana, dan menyita berkas-berkas aktivitas MK, beberapa di antaranya menyebut nama Mandela. Pengadilan Rivonia langsung diselenggarakan di Mahkamah Agung Pretoria pada tanggal 9 Oktober. Mandela dan rekan-rekannya dituduh empat kali melakukan sabotase dan konspirasi untuk menggulingkan pemerintah. Kepala jaksa penuntut Percy Yutar menuntut mereka dihukum mati. Hakim Quartus de Wet menutup kasus jaksa dengan alasan bukti tidak cukup, tetapi Yutar menyusun ulang tuntutannya dan mengajukan kasus baru sejak Desember sampai Februari 1964 dengan melibatkan 173 saksi mata dan ribuan dokumen dan foto.
Kecuali James Kantor, yang dinyatakan tidak bersalah atas semua tuduhan, Mandela dan terdakwa lainnya mengaku melakukan sabotase namun menolak pernah sepakat melancarkan perang gerilya terhadap pemerintah. Mereka menegaskan tujuan politik mereka di pengadilan ini; salah satu pidato Mandela—terinspirasi pidato "History Will Absolve Me" oleh Castro—diliput besar-besaran oleh pers meski ada sensor dari pemerintah. Pengadilan ini mendapat perhatian internasional; banyak pihak di seluruh dunia meminta pembebasan para terdakwa, termasuk Perserikatan Bangsa-Bangsa dan World Peace Council. University of London Union menyerukan agar Mandela menjadi presiden dan misa malam untuknya diadakan di St. Paul's Cathedral, London. Apa daya, karena dianggap penyerobot komunis, pemerintah Afrika Selatan mengabaikan tuntutan-tuntutan tersebut, dan pada 12 Juni 1964 de Wet menetapkan empat tuduhan kepada Mandela dan dua terdakwa dan menjatuhkan vonis penjara seumur hidup, bukan hukuman mati.
Mandela dan terdakwa lainnya dipindahkan dari Pretoria ke penjara di Pulau Robben dan dikurung di sana sampai 18 tahun selanjutnya. Terisolasi dari tahanan-tahanan non-politik di Section B, Mandela ditahan di sel beton lembap berukuran kali yang dilengkapi tikar jerami untuk tidur. Selain sering ditindas secara verbal dan fisik oleh penjaga berkulit putih, para tahanan Pengadilan Rivonia menghabiskan waktu dengan memecah batu sampai akhirnya dipindahtugaskan ke tambang batu kapur pada Januari 1965. Mandela awalnya dilarang memakai kacamata, sehingga sinar batu kapur tersebut merusak penglihatannya secara permanen. Malamnya, ia belajar demi mendapatkan gelar LLB tetapi dilarang membaca surat kabar. Ia sempat beberapa kali ditahan di kurungan soliter akibat menyelundupkan kliping berita. Dengan level tahanan terendah, Kelas D, Mandela hanya boleh dijenguk sekali dan mengirim sepucuk surat saja setiap enam bulan, walaupun semua surat yang keluar masuk disensor besar-besaran.
Para tahanan politik bekerja dan mogok makan–cara terakhir dianggap tidak efektif oleh Mandela—demi memperbaiki kondisi penjara dan melihatnya sebagai dunia perjuangan antiapartheid berukuran kecil. Para tahanan ANC mengangkat Mandela sebagai anggota "High Organ" bersama Sisulu, Govan Mbeki, dan Raymond Mhlaba. Mandela juga terlibat dalam sebuah grup yang mewakili semua tahanan politik di pulau itu, Ulundi; dari situ ia membina hubungan dengan anggota PAC dan Yu Chi Chan Club. Setelah merintis "University of Robben Island," tempat para tahanan berceramah tentang bidang yang dikuasainya, ia memperdebatkan topik-topik seperti homoseksualitas dan politik dengan teman-temannya sampai terlibat perdebatan panas soal politik dengan penganut Marxis seperti Mbeki dan Harry Gwala. Meski rajin menghadiri misa Minggu, Mandela juga mempelajari Islam. Ia juga belajar bahasa Afrikaans dengan harapan mampu membuat penjaga penjara mengerti dan mendukung perjuangannya. Sejumlah pejabat menjenguk Mandela, termasuk perwakilan parlemen liberal Helen Suzman dari Partai Progresif yang melanjutkan perjuangan Mandela di luar penjara. Pada September 1970, Mandela dijenguk AP Partai Buruh Britania Raya Dennis Healey. Menteri Kehakiman Afrika Selatan Jimmy Kruger berkunjung bulan Desember 1974, namun Healey dan Mandela gagal menemuinya. Ibu Mandela berkunjung tahun 1968 dan meninggal tidak lama kemudian. Putra pertama Mandela, Thembi, meninggal dunia akibat kecelakaan mobil setahun berikutnya; Mandela dilarang menghadiri pemakaman ibu maupun putranya. Istrinya jarang menjenguk karena sering dipenjara akibat aktivitas politiknya, sementara putri-putrinya pertama menjenguk Mandela bulan Desember 1975; Winnie keluar penjara tahun 1977 namun dipaksa menetap di Brandfort, sehingga tidak bisa menjenguk ayahnya.
Sejak 1967, kondisi penjara membaik, tahanan berkulit hitam diberikan celana panjang (sebelumnya celana pendek), permainan boleh diselenggarakan, dan kualitas makanan meningkat. Pada 1969, rencana kabur untuk Mandela disusun oleh Gordon Bruce, namun dibatalkan setelah diketahui agen South African Bureau of State Security (BOSS) yang ingin melihat Mandela ditembak saat kabur. Tahun 1970, Komandan Piet Badenhost mengambil alih kendali. Merasa penyiksaan fisik dan mental terhadap tahanan meningkat, Mandela menyampaikan keluhannya ke hakim-hakim yang berkunjung; Badenost akhirnya dipindahtugaskan. Ia digantikan oleh Komandan Willie Willemse yang membina hubungan baik dengan Mandela dan mau memperbaiki standar penjara. Pada 1975, Mandela menjadi tahanan Kelas A, sehingga ia berhak mendapat jatah kunjungan dan surat yang lebih besar; ia menghubungi para aktivis antiapartheid seperti Mangosuthu Buthelezi dan Desmond Tutu. Tahun itu pula, ia mulai menulis otobiografi yang kemudian diselundupkan ke London, namun tidak diterbitkan; otoritas penjara menemukan beberapa lembar halaman dan hak belajar Mandela dihentikan selama empat tahun. Ia lantas menghabiskan waktunya dengan berkebun dan membaca sampai melanjutkan studi LLB-nya tahun 1980.
Pada akhir 1960-an, ketenaran Mandela dikalahkan oleh Steve Biko dan Black Consciousness Movement (BCM). Menganggap ANC tidak efektif, BCM menyerukan aksi militan, tetapi setelah pemberontakan Soweto tahun 1976 banyak aktivis BCM yang dipenjara di Pulau Robben. Mandela mencoba membangun hubungan dengan radikal-radikal muda ini, meski kritis terhadap rasialisme dan ketidaksukaan mereka terhadap aktivis antiapartheid berkulit putih. Ketertarikan dunia internasional terhadap perjuangannya bermula bulan Juli 1978, bertepatan dengan ulang tahun Mandela ke-60. Ia mendapatkan gelar doktoral kehormatan di Lesotho, Nehru Prize for International Understanding di India tahun 1970, dan Freedom of the City di Glasgow, Skotlandia, tahun 1980. Pada Maret 1980, slogan "Free Mandela!" dicetuskan oleh jurnalis Percy Qoboza dan mengawali kampanye internasional yang memaksa Dewan Keamanan PBB menuntut pembebasannya. Walaupun tekanan luar negeri sangat besar, pemerintah menolak dan bergantung pada sekutu Perang Dingin yang kuat seperti Presiden Amerika Serikat Ronald Reagan dan Perdana Menteri Britania Raya Margaret Thatcher; Thatcher menganggap Mandela teroris komunis dan mendukung penekanan terhadap ANC.
Bulan April 1982, Mandela ditransfer ke Penjara Pollsmoor di Tokai, Cape Town bersama sejumlah pemimpin senior ANC Walter Sisulu, Andrew Mlangeni, Ahmed Kathrada, dan Raymond Mhlaba; mereka yakin sedang diisolasi demi menghapus pengaruh mereka terhadap aktivis-aktivis muda. Kondisi di Pollsmoor lebih baik ketimbang Pulau Robben, tetapi Mandela merasa rindu camaraderie dan pemandangan pulau tersebut. Berteman dengan kepala sipir Pollsmoor, Brigadir Munro, Mandela diizinkan membuat kebun atap, serta membaca besar-besar dan mendapat jatah 52 surat setahun. Ia ditunjuk sebagai pelindung gerakan multiras Front Demokratik Bersatu (UDF) yang didirikan untuk melawan reformasi pemerintahan Presiden Afrika Selatan P.W. Botha. Pemerintah Partai Nasional pimpinan Botha mengizinkan warga Kleurlinge dan India memilih perwakilannya sendiri yang kelak mengatur pendidikan, kesehatan, dan perumahan, namun orang Afrika kulit hitam dikecualikan dari sistem ini; layaknya Mandela, UDF memandang hal ini sebagai upaya memecah gerakan antiapartheid di sektor ras.
Kekerasan di seluruh negeri meningkat. Banyak orang mengkhawatirkan pecah perang saudara. Di bawah tekanan lobi internasional, bank-bank multinasional berhenti berinvestasi di Afrika Selatan, mengakibatkan stagnasi ekonomi. Beberapa bank dan Thatcher menuntut Botha membebaskan Mandela—pada puncak ketenaran internasionalnya—untuk meredam situasi yang tidak stabil ini. Walaupun menganggap Mandela "Marxis besar" yang berbahaya, pada Februari 1985 Botha menawarkan pembebasannya dari penjara dengan syarat ia "menolak kekerasan tanpa syarat sebagai senjata politik". Mandela menolaknya dan merilis pernyataan melalui putrinya, Zindzi, bahwa "Kebebasan apa yang sedang ditawarkan kepadaku jika organisasi rakyat [ANC] tetap dilarang? Hanya orang bebas yang dapat bernegosiasi. Seorang tahanan tidak boleh terlibat kesepakatan."
Pada tahun 1985, Mandela menjalani operasi terhadap pembesaran kelenjar prostat sebelum ditempatkan di sel soliter baru di lantai bawah. Ia bertemu "tujuh orang penting", yaitu delegasi internasional yang dikirimkan untuk menegosiasikan penyelesaian kasus, tetapi pemerintah Botha menolak kerja sama. Bulan Juni tahun itu, pemerintah menyatakan keadaan darurat dan mengizinkan polisi meredam kerusuhan tersebut. Pemberontak antiapartheid melawan; ANC melakukan 231 serangan tahun 1836 dan 235 serangan tahun 1987. Dengan pasukan darat dan paramiliter sayap kanan untuk melawan pemberontak, pemerintah diam-diam mendanai gerakan nasionalis Zulu, Inkatha, untuk menyerang anggota-anggota ANC yang lantas memperparah tindak kekerasan. Mandela meminta diskusi dengan Botha tapi ditolak, malah bertemu secara rahasia dengan Menteri Kehakiman Kobie Coetsee pada 1987, lalu bertemu lagi sebanyak 11 kali selama 3 tahun. Coetsee mengatur negosiasi antara Mandel dengan satu tim beranggotakan empat pejabat pemerintah sejak Mei 1988; tim sepakat membebaskan tahanan politik dan mengesahkan ANC dengan syarat mereka tidak boleh lagi melancarkan aksi kekerasan, memutus 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 100.000 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 1.600 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.
Pasca pembantaian Bisho, yaitu penembakan oleh Ciskei Defence Force terhadap 28 pendukung ANC dan 1 tentara saat unjuk rasa, Mandela menyadari bahwa aksi massal berujung pada kekerasan lebih lanjut dan melanjutkan negosiasi pada bulan September. Ia menyetujuinya dengan syarat semua tahanan politik dibebaskan, senjata tradisional Zulu dilarang, dan hostel-hostel Zulu dipagari, dua syarat terakhir bertujuan mencegah serangan Inkatha selanjutnya; karena ditekan terus-menerus, de Klerk mau tidak mau setuju. Negosiasi ini menyepakati pemilu multiras akan diselenggarakan, yang kemudian membentuk pemerintahan koalisi persatuan nasional selama lima tahun dan majelis konstitusional yang memberi Partai Nasional pengaruh besar. ANC juga setuju melindungi pekerjaan para pegawai negeri kulit putih; konsesi semacam itu dikritik habis-habisan di dalam negeri. Keduanya menyetujui konstitusi interim, menjamin pemisahan kekuasaan, mendirikan pengadilan konstitusi, dan undang-undang hak asasi manusia bergaya Amerika Serikat. Negosiasi ini juga membagi negara ini menjadi sembilan provinsi, masing-masing dengan pemimpin dan pelayanan sipilnya sendiri, kesepakatan di antara keinginan federalisme de Klerk dan pemerintah kesatuan Mandela.
Proses demokratis ini terancam oleh Concerned South Africans Group (COSAG), aliansi partai-partai Afrikaner sayap kanan dan kelompok separatis kulit hitam seperti Inkatha; pada Juni 1993, kelompok supremasis kulit putih Afrikaner Weerstandsbeweging (AWB) menyerang Kempton Park World Trade Centre. Pasca pembunuhan ketua ANC Chris Hani, Mandela berpidato untuk meredam kerusuhan, sesaat setelah muncul di pemakaman massal di Soweto mewakili Tambo yang meninggal akibat stroke. Bulan Juli 1993, Mandela dan de Klerk sama-sama berkunjung ke Amerika Serikat, bertemu Presiden Bill Clinton secara terpisah dan masing-masing mendapatkan Liberty Medal. Tidak lama kemudian, mereka sama-sama mendapatkan Hadiah Perdamaian Nobel di Norwegia. Dipengaruhi ketua ANC yang muda, Thabo Mbeki, Mandela mulai bertemu tokoh-tokoh bisnis besar dan membungkam dukungannya untuk nasionalisasi, khawatir ia akan menakut-nakuti investor asing yang sangat diperlukan. Meski dikritisi anggota-anggota ANC yang sosialis, ia didorong memboyong perusahaan swasta oleh anggota partai Komunis Cina dan Vietnam di World Economic Forum Januari 1992 di Swiss. Mandela juga tampil kameo sebagai guru sekolah yang membacakan salah satu pidato Malcolm X di adegan terakhir film "Malcolm X" (1992).
Dengan penetapan pemilu pada tanggal 27 April 1994, ANC mulai berkampanye, membuka 100 posko pemilu, dan mempekerjakan penasihat Stanley Greenberg. Greenberg merancang pondasi People's Forums di seluruh negeri, sehingga Mandela bisa tampil; meski merupakan pembicara publik yang buruk, Greenberg adalah tokoh terkenal dengan status tinggi di kalangan penduduk kulit hitam Afrika Selatan. ANC mengampanyekan Reconstruction and Development Programme (RDP), yaitu program pembangunan satu juta rumah dalam lima tahun, penciptaan pendidikan gratis universal, dan perluasan akses air bersih dan listrik. Slogan partai ini adalah ""a better life for all"" (kehidupan yang lebih baik untuk semua), walaupun tidak dijelaskan dari mana pendanaannya. Selain "Weekly Mail" dan "New Nation", pers Afrika Selatan menentang pencalonan Mandela, mengkhawatirkan konflik etnis, dan mendukung Partai Nasional atau Partai Demokrat. Mandela menghabiskan banyak waktu untuk menggalang dana untuk ANC, keliling Amerika Utara, Eropa, dan Asia untuk bertemu donatur-donatur kaya, termasuk mantan pendukung rezim apartheid. Ia juga mengusulkan pengurangan batas usia memberi suara dari 18 tahun menjadi 14; setelah ditolak ANC, kebijakan ini menjadi bahan tertawaan.
Khawatir bahwa COSAG akan mengacaukan pemilu, terutama pasca Pertempuran Bop dan Pembantaian Shell House—masing-masing kekerasan yang melibatkan AWB dan Inkatha—Mandela bertemu beberapa politikus dan jenderal Afrikaner, termasuk P.W. Botha, Pik Botha, dan Constand Viljoen, membujuk mereka untuk ikut sistem demokrasi, dan de Klerk meyakinkan Buthelezi dari Inkatha untuk ikut pemilu alih-alih melancarkan perang separatis. Selaku ketua kedua partai besar tersebut, de Klerk dan Mandela tampil dalam acara debat televisi; meskipun de Kler dianggap luas sebagai pembicara terbaik di acara ini, tawaran Mandela untuk bersalaman mengejutkannya, sehingga banyak komentator menganggap Mandela-lah yang menang. Pemilihan umum berlangsung dengan sedikit aksi kekerasan, termasuk bom mobil sel AWB yang menewaskan 20 orang. Mandela memberi suara di Ohlange High School di Durban, dan meski menjadi Presiden terpilih, ia mengaku secara terbuka bahwa pemilu ini penuh penipuan dan sabotase. Dengan 62% suara nasional, ANC tinggal sedikit lagi mencapai dua pertiga mayoritas yang diperlukan untuk mengubah konstitusi. ANC juga menang di 7 provinsi, sementara masing-masing Inkatha dan Partai Nasional 1 provinsi.
Pelantikan Mandela dilangsungkan di Pretoria pada tanggal 10 Mei 1994, disiarkan ke satu miliar penonton di seluruh dunia. Acara ini dihadiri 4.000 tamu, termasuk pemimpin dunia dari berbagai latar belakang. Selain Presiden Afrika Selatan berkulit hitam pertama, Mandela juga menjadi kepala Pemerintah Persatuan Nasional yang didominasi ANC—yang justru tidak punya pengalaman di pemerintahan—tetapi juga melibatkan perwakilan Partai Nasional dan Inkatha. Sesuai perjanjian sebelumnya, de Klerk menjadi Wakil Presiden pertama, sedangkan Thabo Mbeki sebagai wakil pada masa jabatan kedua. Meski Mbeki bukan pilihan pertamanya untuk jabatan ini, Mandela menjadi sangat bergantung padanya sepanjang masa pemerintahannya dan mengizinkan Mbeki menyusun rincian kebijakan. Setelah pindah ke kantor presiden di Tuynhuys di Cape Town, Mandela mengizinkan de Klerk tetap di kediaman kepresidenan di puri Groote Schuur, bukan di puri Westbrooke yang berganti nama menjadi "Genadendal" yang berarti "Lembah Pertolongan" dalam bahasa Afrikaans. Selain mempertahankan rumahnya di Houghton, ia juga membangun rumah di kampung halamannya, Qunu. Ia sering berkunjung ke Qunu, jalan-jalan di sana, bertemu warga setempat, dan memutuskan sengketa suku.
Pada usia 76 tahun, ia menghadapi berbagai penyakit, dan walaupun memiliki cukup tenaga, ia merasa terisolasi dan ditinggal sendirian. Ia sering menghibur selebritis, seperti Michael Jackson, Whoopi Goldberg, dan Spice Girls. Ia juga berteman dengan sejumlah pebisnis kaya seperti Harry Oppenheimer dari Anglo-American, dan ratu Britania Raya Elizabeth II dalam kunjungan kenegaraannya ke Afrika Selatan bulan Maret 1995, sehingga Mandela dihujani kritik dari penganut antikapitalis di ANC. Meski orang-orang sekitarnya hidup berkecukupan, Mandela hidup sederhana dan menyumbangkan sepertiga gaji tahunannya sebesar 552.000 rand ke Nelson Mandela Children's Fund yang ia dirikan tahun 1995. Walaupun berbicara lantang mendukung kebebasan pers dan berteman dengan banyak jurnalis, Mandela kritis terhadap sebagian besar media di negaranya karena dimiliki dan dioperasikan penduduk kulit putih kelas menengah dan yakin mereka terlalu fokus menakut-nakuti penonton dengan berita kejahatan. Setelah duduk di kursi presiden, Mandela ganti baju beberapa kali sehari dan salah satu merek dagang Mandela adalah kemeja batiknya yang dikenal sebagai "kemeja Madiba". Ia selalu memakainya bahkan dalam suasana formal.
Bulan Desember 1994, otobiografi Mandela, "Long Walk to Freedom", akhirnya diterbitkan. Pada akhir 1994, ia menghadiri konferensi ANC ke-49 di Bloemfontein. Di sana Eksekutif Nasional yang lebih militan dipilih, termasuk di antaranya Winnie Mandela; meski Winnie tertarik rujuk, Nelson memulai proses perceraian pada Agustus 1995. Tahun 1995, ia menjalin hubungan dengan Graça Machel, aktivis politik Mozambik yang 27 lebih muda dan merupakan janda mantan presiden Samora Machel. Mereka pertama bertemu bulan Juli 1990 ketika Machel masih berduka, namun persahabatan mereka berkembang menjadi pasangan kekasih. Machel sering menemani Mandela dalam kunjungannya ke luar negeri. Ia menolak lamaran pernikahan pertama Mandela karena ingin lebih bebas dan bisa membagi waktunya antara Mozambik dan Johannesburg.
Memimpin transisi dari kekuasaan minoritas apartheid ke demokrasi multikultural, Mandela melihat rekonsiliasi nasional sebagai tugas utama pemerintahannya. Setelah melihat negara-negara Afrika pasca-kolonial hancur akibat ditinggalkan elit kulit putih, Mandela berusaha menjamin populasi kulit putih Afrika Selatan bahwa mereka dilindungi dan diwakili di "Bangsa Pelangi" ini. Mandela berupaya menciptakan koalisi seluas mungkin di kabinetnya. De Klerk menjadi Wakil Presiden pertama, sedangkan pejabat-pejabat Partai Nasional lainnya menjadi menteri Pertanian, Energi, Lingkungan, dan Mineral dan Energi, dan Buthelezi menjadi Menteri Dalam Negeri. Jabatan kabinet yang lain diduduki anggota ANC, kebanyakan di antaranya—seperti Joe Modise, Alfred Nzo, Joe Slovo, Mac Maharaj, dan Dullah Omar—adalah teman seperjuangan, meski yang lainnya seperti Tito Mboweni dan Jeff Radebe justru jauh lebih muda. Hubungan Mandela dengan de Klerk renggang; Mandela menduga de Klerk sengaja provokatif, sementara de Klerk merasa ia sengaja dipermalukan oleh presiden. Pada Januari 1995, Mandela mengkritik habis-habisan de Klerk karena memberikan amnesti kepada 3.500 polisi tepat sebelum pemilu, dan kemudian mengkritiknya karena melindungi mantan Menteri Pertahanan Magnus Malan yang dituduh melakukan pembunuhan.
Mandela secara pribadi bertemu tokoh-tokoh senior rezim apartheid, termasuk janda Hendrik Verwoerd Betsie Schoombie dan pengacara Percy Yutar; menekankan pemberian maaf dan rekonsiliasi pribadinya, ia mengumumkan bahwa "orang-orang berani tidak takut memberi maaf demi perdamaian." Ia mendorong penduduk kulit hitam Afrika Selatan mendukung tim nasional rugbi yang sebelumnya dibenci, Springboks, saat Afrika Selatan menjadi tuan rumah Piala Dunia Rugbi 1995. Setelah Springboks memenangkan final melawan Selandia Baru, Mandela mempersembahkan trofinya ke kapten Francois Pienaar, seorang Afrikaner, sambil mengenakan baju Sprinboks dengan nomor 6 miliki Pienaar di belakangnya. Hal ini dipandang luas sebagai loncatan besar rekonsiliasi penduduk kulit putih dan hitam Afrika Selatan; seperti yang dikatakan de Klerk, "Mandela memenangkan hati jutaan penggemar rugbi berkulit putih." Upaya rekonsiliasi Mandela meredam rasa takut masyarakat kulit putih, namun juga mendapat kritik dari kaum militan kulit hitam. Mantan istrinya, Winnie, menuduh ANC lebih tertarik memuaskan orang kulit putih ketimbang membantu orang kulit hitam.
Kontroversialnya lagi, Mandela terlibat dalam pembentukan Komisi Kebenaran dan Rekonsiliasi untuk menyelidiki kejahatan-kejahatan era apartheid oleh pemerintah dan ANC dan menunjuk Desmond Tutu sebagai ketuanya. Untuk mencegah munculnya martir, Komisi ini memberikan amnesti individu dengan imbalan kesaksian kejahatan yang dilakukan selama era apartheid. Didirikan bulan Februari 1996, Komisi ini mengadakan dengar pendapat selama dua tahun yang merincikan kasus pemerkosaan, penyiksaan, pengeboman, dan pembunuhan, sebelum menerbitkan laporan terakhirnya pada Oktober 1998. Baik de Klerk dan Mbeki menuntut sebagian laporan tersebut dihapus, tetapi hanya tuntutan de Klerk yang dipenuhi. Mandela memuji kerja Komisi sambil menyatakan mereka "telah membantu kita beralih dari masa lalu untuk berkonsentrasi pada masa kini dan masa depan".
Pemerintahan Mandela mewarisi negara dengan kesenjangan kekayaan dan jasa yang sangat besar di kalangan masyarakat kulit putih dan hitam. Dengan populasi 40 juta orang, kurang lebih 23 juta di antaranya tidak terhubung dengan listrik atau sanitasi memadai, 12 juta orang tidak punya suplai air bersih, dan 2 juta anak tidak bersekolah dan sepertiga penduduknya buta huruf. 33% rakyat menganggur dan nyaris separuh populasi hidup di bawah garis kemiskinan. Cadangan keuangan pemerintah hampir habis dan seperlima anggaran nasional dihabiskan untuk bayar utang, artinya cakupan Program Rekonstruksi dan Pembangunan (RDP) yang dijanjikan harus disusutkan dan tidak ada nasionalisasi atau penciptaan lapangan kerja. Pemerintah malahan mengadopsi kebijakan ekonomi liberal untuk mempromosikan investasi asing, mengikuti "konsensus Washington" yang dikeluarkan Bank Dunia dan International Monetary Fund.
Di bawah pemerintahan Mandela, anggaran kesejahteraan naik 13% tahun 1996/97, 13% tahun 1997/98, dan 7% tahun 1998/99. Pemerintah memperkenalkan kesetaraan bantuan untuk masyarakat, termasuk bantuan orang cacat, bantuan perawatan anak, serta dana pensiun lansia, yang sebelumnya diberi tingkatan-tingkatan untuk berbagai kelompok ras Afrika Selatan. Tahun 1994, layanan kesehatan gratis diberikan untuk anak-anak di bawah usia 6 tahun dan ibu hamil, suatu peraturan yang cakupannya diperluas sampai semua pengguna layanan kesehatan sektor publik tingkat dasar pada tahun 1996. Pada pemilu 1999, ANC mengatakan bahwa karena kebijakan mereka, 3 juta orang terhubung ke telepon, 1,5 juta anak mengenyam pendidikan, 500 klinik diperbarui atau dibangun, 2 juta orang terhubung ke listrik, akses air bersih diperluas samapai 3 juta orang, dan 750.000 rumah dibangun dengan total penghuni nyaris 3 juta orang.
Undang-Undang Pengembalian Lahan 1994 memungkinkan masyarakat yang kehilangan propertinya akibat Undang-Undang Tanah Prbumi 1913 mengklaim balik tanah mereka. Puluhan ribu orang berhasil menyelesaikan klaim tanah mereka. UU Reformasi Lahan 3 tahun 1996 melindungi hak-hak penyewa pekerja yang tinggal dan menanam hasil bumi atau beternak di peternakan. Undang-undang ini menjamin penyewa tidak dapat diusir tanpa perintah pengadilan atau usianya melebihi 65 tahun. UU Pengembangan Kemampuan 1998 menetapkan serangkaian mekanisme untuk mendanai dan mempromosikan pengembangan kemampuan di tempat kerja. UU Hubungan Tenaga Kerja 1995 mempromosikan demokrasi di tempat kerja, perundingan bersama secara tertib, serta penyelesaian efektif sengketa tenaga kerja. UU Persyaratan Dasar Pekerjaan 1997 memperbaiki mekanisme kerja serta memperluas "cakupan" hak ke semua pekerja, sedangkan UU Kesetaraan Pekerjaan 1998 disahkan untuk mengakhiri diskriminasi tidak adil dan menjamin implementasi tindakan yang disetujui di tempat kerja.
Sayangnya banyak masalah di dalam negeri. Sejumlah kritikus seperti Edwin Cameron menuduh pemerintah Mandela berbuat sedikit untuk meredam wabah HIV/AIDS di negara itu; tahun 1999, 10% penduduk Afrika Selatan dinyatakan positif mengidap HIV. Mandela kelak mengakui bahwa ia secara pribadi mengabaikan masalah ini dan menyutuh Mbeki menanganinya. Mandela juga mendapat kritik karena gagal memberantas kejahatan, karena itu pula Afrika Selatan memiliki salah satu tingkat kejahatan tertinggi di dunia; ini juga alasan utama yang dikatakan 750.000 orang kulit putih yang beremigrasi pada akhir 1990-an. Pemerintahan Mandela dibanjiri skandal korupsi dan Mandela sendiri dianggap "lembek" terhadap korupsi dan kerakusan.
Mencontoh Afrika Selatan, Mandela mendorong negara-negara lain menyelesaikan konflik melalui diplomasi dan rekonsiliasi. Ia mengulang seruan Mbeki untuk "Renaisans Afrika" dan sangat memedulikan masalah di benua ini. Ia mengambil pendekatan diplomatik lembut untuk menurunkan junta militer Sani Abacha di Nigeria namun justru menjadi tokoh utama yang menuntut sanksi ketika rezim Abacha terus-terusan melanggar hak asasi manusia. Tahun 1996, ia ditunjuk sebagai Ketua Southern African Development Community (SADC) dan memulai negosiasi pengakhiran Perang Kongo Pertama di Zaire yang kemudian terbukti gagal. Dalam operasi militer pasca-apartheid pertama Afrika Selatan, Mandela memerintahkan tentara masuk Lesotho pada September 1998 untuk melindungi pemerintahan Perdana Menteri Pakalitha Mosisili setelah sengketa pemilu memicu pemberontakan oposisi.
Pada September 1998, Mandela ditunjuk sebagai Sekretaris Jenderal Gerakan Non-Blok dan mengadakan konferensi tahunannya di Durban. Ia memanfaatkan acara ini untuk mengkritik "kepentingan sempit dan chauvinistik" pemerintah Israel karena menghambat negosiasi untuk mengakhiri konflik Israel-Palestina dan memaksa India dan Pakistan berunding untuk mengakhiri konflik Kashmir, dan karena itu pula ia dikritik oleh Israel dan India. Terinspirasi oleh ledakan ekonomi di kawasan ini, Mandela mempererat hubungan ekonominya dengan Asia Timur, terutama dengan Malaysia, walaupun terganggu oleh krisis keuangan Asia 1997. Ia memicu kontroversi karena berteman dekat dengan Presiden Indonesia Suharto, yang rezimnya bertanggung jawab atas sejumlah besar pelanggaran hak asasi manusia. Mandela secara pribadi membujuk Suharto agar menarik pasukannya dari Timor Timur.
Mandela menghadapi kritik serupa dari dunia barat karena berteman dengan Fidel Castro dan Muammar Gaddafi. Castro berkunjung ke Afrika Selatan tahun 1998 dan disambut masyarakat, sedangkan Mandela bertemu Gaddafi di Libya untuk menganugerahkan Order of Good Hope kepadanya. Saat pemerintah dan media barat mengkritik kunjungan-kunjungan tersebut, Mandela menyebut kritik tersebut bernada rasis. Mandela berharap bisa menyelesaikan masalah yang tak kunjung uai antara Libya dan Amerika Serikat dan Britania seputar pengadilan dua warga Libya, Abdelbaset al-Megrahi dan Lamin Khalifah Fhimah, yang diadili bulan November 1991 dan dituduh menyabotase Pan Am Penerbangan 103. Mandela mengusulkan mereka diadili di negara ketiga yang disetujui semua pihak terlibat. Mengikuti hukum Skotlandia, pengadilan ini diselenggarakan di Camp Zeist di Belanda pada April 1999 dan menyatakan salah satunya bersalah.
Konstitusi Afrika Selatan yang baru disetujui parlemen pada bulan Mei 1996. Konstitusi ini menetapkan serangkaian institusi untuk mengawasi kewenangan politik dan administratif di dalam bingkai demokrasi konstitusional. De Klerk tetap saja menentang penerapan konstitusi ini dan menarik diri dari pemerintah koalisi sebagai bentuk protes. ANC mengambil alih jabatan-jabatan kabinet yang sebelumnya dipegang Partai Nasional; Mbeki menjadi Wakil Presiden tunggal. Andai suatu hari Mandela bersama Mbkei berada di luar negeri, Buthelezi ditunjuk sebagai "Presiden Sementara". Ini menandakan adanya perbaikan hubungan antara dirinya dengan Mandela.
Mandela mengundurkan diri sebagai Presiden ANC pada konferensi Desember 1997, dan meski berharap Ramaphosa akan menggantikannya, ANC memilih Mbeki sebagai presiden; Mandela mengaku bahwa saat itu Mbeki telah menjadi "Presiden negara secara "de facto"". Menggantikan Mbeki sebagai Wakil Presiden, Mandela dan Eksekutif mendukung pencalonan Jacob Zuma, seorang Zulu yang sempat dipenjara di Pulau Robben, tetapi ia ditantang Winnie, yang retorika populisnya memberinya banyak pengikut di dalam partai; Zuma mengalahkannya dengan telak di pemilu.
Hubungan Mandela dengan Machel semakin intensif; pada Februari 1998 ia menyatakan bahwa "Aku jatuh cinta dengan seorang wanita yang luar biasa", dan di bawah tekanan sahabatnya Desmond Tutu, yang memaksanya menjadi panutan bagi para pemuda, ia mengadakan pernikahan pada ulang tahun Mandela ke-80 bulan Juli. Keesokan harinya, ia mengadakan pesta besar yang dihadiri beberapa tamu asing. Mandela tidak pernah berencana mencalonkan diri untuk kedua kalinya dan menyampaikan pidato perpisahan pada 29 Maret 1999. Setelah itu ia pensiun.
Pensiun bulan Juni 1999, Mandela memilih kehidupan keluarga yang sunyi, terbagi antara Johannesburg dan Qunu. Ia hendak menulis sekuel otobiografinya yang berjudul "The Presidential Years", tetapi ditinggalkan begitu saja sebelum diterbitkan. Karena menganggap hidup sendiri sulit, ia beralih ke kehidupan publik yang sibuk dengan program harian penuh tugas, bertemu pemimpin dunia dan selebriti, dan di Johannesburg bekerja dengan Nelson Mandela Foundation yang didirikan tahun 1999 untuk berfokus pada pemberantasan HIV/AIDS, pembangunan desa, dan pembangunan sekolah. Walaupun dihujani kritik karena gagal melakukan hal yang sepantasnya untuk mencegah wabah tersebut selama masa pemerintahannya, ia menghabiskan banyak waktunya untuk masalah ini setelah pensiun dan menyebutnya "perang" yang menewaskan lebih dari "perang-perang sebelumnya". Ia juga meminta pemerintahan Mbeki menjamin warga Afrika Selatan yang terjangkit HIV+ mendapatkan retrovirus. Tahun 2000, turnamen golf amal Nelson Mandela Invitational diadakan dan dibawakan oleh Gary Player. Mandela berhasil sembuh dari kanker prostat pada bulan Juli 2001.
Pada tahun 2002, Mandela meresmikan Nelson Mandela Annual Lecture, dan Mandela Rhodes Foundation dibentuk tahun 2003 di Rhodes House, University of Oxford, untuk menyediakan beasiswa pascasarjana kepada mahasiswa-mahasiswa Afrika. Proyek-proyek ini diikuti oleh Nelson Mandela Centre of Memory dan kampanye 46664 melawan HIV/AIDS. Ia menyampaikan pidato penutup di XIII International AIDS Conference di Durban tahun 2000, dan pada 2004, ia berbicara di XV International AIDS Conference di Bangkok, Thailand.
Secara terbuka, Mandela semakin lantang mengkritik negara-negara Barat. Ia sangat menentang intevensi NATO di Kosovo tahun 1999 dan menyebutnya upaya bangsa-bangsa kuat dunia untuk menjadi polisi dunia. Pada tahun 2003, ia menentang rencana Amerika Serikat dan Britania Raya melancarkan perang di Irak, menyebutnya "tragedi" dan mengecam Presiden AS George W. Bush dan Perdana Menteri Britania Tony Blair karena meremehkan PBB. Ia umumnya lebih menyerang AS, menegaskan bahwa negara tersebut melakukan "kekerasan yang sangat tak terhitung" di seluruh dunia ketimbang negara lain sambil menyebut pengeboman atom di Jepang; pernyataan ini memicu kontroveris internasional, meski ia tetap melanjutkan hubungannya dengan Blair. Tertarik dengan hubungan Libya-Britania, ia menjenguk Megrahi di penjara Barlinnie dan tidak menerima perlakuan terhadapnya; ia menyebut perlakuan tersebut "siksaan psikologis."
pada bulan Juni 2004, pada usia 85 tahun dan kesehatan yang memburuk, Mandela mengumumkan bahwa ia "pensiun dari masa pensiun" dan menarik diri dari kehidupan publik seraya mengatakan "Jangan panggil aku, aku yang akan memanggilmu." Meski terus bertemu teman dekat dan keluarga, Foundation terus menolak undangan agar Mandela tampil di acara-acara publik dan menolak sebagian besar permintaan wawancara. Ia tetap terlibat dalam urusan internasional dan mendorong Presiden Zimbabwe Robert Mugabe mengundurkan diri karena meningkatnya pelanggaran hak asasi manusia di negara itu. Setelah terbukti tidak efektif, ia berbicara lantang menentang Mugabe pada tahun 2007, memintanya turun "dengan penuh rasa hormat dan martabat." Tahun itu, Mandela, Machel, dan Desmond Tutu mengumpulkan para pemimpin dunia di Johannesburg untuk menyumbangkan pemikiran dan kepemimpinan independen mereka untuk menyelesaikan sejumlah masalah tersulit di dunia. Mandela mengumumkan pembentukan grup barunya, The Elders, dalam sebuah pidato yang disampaikan pada ulang tahun ke-89.
Ulang tahun Mandela ke-90 dirayakan di seluruh Afrika Selatan pada 18 Juli 2008. Pesta utamanya diadakan di Qunu dan konser penghormatan kepadanya diselenggarakan di Hyde Park, London. Dalam pidato acara tersebut, Mandela meminta semua orang kaya membantu orang miskin di seluruh dunia. Sepanjang masa pemerintahan Mbeki, Mandela terus mendukung ANC, meski biasanya dibayang-bayangi Mbeki di setiap acara publik yang dihadiri keduanya. Mandela lebih mudah bersosialisasi dengan pengganti Mbeki Jacob Zuma, walaupun Nelson Mandela Foundation kecewa karena cucunya, Kepala Suku Mandla Mandela, menerbangkannya ke Eastern Cape untuk menghadiri rapat umum pro-Zuma di tengah badai pada tahun 2009.
Sejak 2004, Mandela berhasil berkampanye agar Afrika Selatan menjadi tuan rumah Piala Dunia FIFA 2010 seraya menyatakan bahwa di sana "ada hadiah yang lebih baik bagi kita pada tahun" peringatan satu dasawarsa sejak jatuhnya apartheid. Meski tetap tertutup sepanjang acara, Mandela untuk pertama kalinya tampil pada upacara penutupan dan mendapat "sambutan yang menggembirakan hari".
Bulan Februari 2011, ia sempat diinapkan di rumah sakit akibat infeksi pernapasan sebelum diinapkan kembali akibat infeksi paru-paru dan pengangkatan batu empedu pada Desember 2012. Setelah prosedur medis berhasil pada awal Maret 2013, infeksi paru-parunya kambuh kembali dan ia dilarikan ke rumah sakit di Pretoria.
Pada 8 Juni 2013, infeksi paru-parunya memburuk dan ia dilarikan kembali ke rumah sakit Pretoria dalam keadaan serius. Setelah empat hari, dilaporkan bahwa ia stabil dan berada dalam "kondisi serius namun stabil". Dalam perjalanan ke rumah sakit, ambulansnya mogok dan terjebak di pinggir jalan selama 40 menit; pemerintah Afrika Selatan dikritik atas insiden tersebut setelah mengonfirmasi laporannya beberapa minggu kemudian, tetapi Presiden Jacob Zuma melawan balik bahwa "Ada tujuh dokter di konvoi tersebut yang memegang kendali penuh atas situasi waktu itu. Ia mendapatkan perawatan medis dari para ahli."
Pada tanggal 22 Juni 2013, CBS News menyatakan bahwa ia belum membuka mata berhari-hari dan tidak responsif, dan keluarganya membahas betapa banyak intervensi medis yang harus diberikan. Tanggal 23 Juni 2013, Presiden Jacob Zuma merilis pernyataan bahwa kondisi Mandela semakin "kritis". Zuma, ditemani Wakil Presiden ANC, Cyril Ramaphosa, bertemu istri Mandela Graça Machel di rumah sakit di Pretoria dan membahas kondisinya. Tanggal 25 Juni, Uskup Agung Cape Town Thabo Makgoba menjenguk Mandela di rumah sakit dan berdoa bersama Graça Machel Mandela "pada waktu sulit untuk menyaksikan dan menunggu". Keesokan harinya, Zuma menjenguk Mandela dan membatalkan kunjungan esok harinya ke Mozambik. Kerabat Mandela memberitahu "The Daily Telegraph" bahwa ia memakai mesin pendukung hidup.
Pada 5 Desember 2013, Mandela meninggal dunia pada usia 95 tahun. Ia meninggal pada pukul 20.50 waktu setempat (UTC+2) di rumahnya yang terletak di Houghton, Johannesburg, dan dikelilingi oleh keluarganya. Secara publik Zuma mengumumkan kematiannya melalui televisi. Jasad Mandela disemayamkan pada tanggal 11 hingga 13 Desember di Union Buildings dan pemakaman kenegaraan dilaksanakan pada 15 Desember di Qunu. Rumah Mandela senilai $4.1 juta diserahkan kepada isterinya, anggota keluarga lain, staf, dan institusi pendidikan.
Di seluruh dunia, Mandela terlihat seperti "otoritas moral' yang memiliki "kepedulian terhadap kebenaran" yang besar. Dianggap ramah, Mandela tampak "santai" ketika berbicara dengan orang lain, termasuk para saingannya. Meski sering berteman dengan miliuner dan tamu penting, ia menikmati berbicara dengan staf-staf mereka saat menjalankan tugas resmi. Di kehidupan akhirnya, ia dikenal mencari hal terbaik dari setiap orang, bahkan mempertahankan saingan politiknya sebagai sekutunya; beberapa orang menganggapnya terlalu mempercayai orang lain. Ia terkenal karena keras kepala dan kesetiaannya, dan memiliki "temperamen panas" yang dapat meledak menjadi amarah dalam situasi tertentu, serta "murung dan gundah" ketika menjauhi mata publik. Ia juga memiliki rasa humor dan sering jahil. Dalai Lama ke-14 adalah teman lama mantan presiden Nelson Mandela.
Sangat sadar akan citranya, sepanjang hidupnya Mandela memakai pakaian-pakaian berkualitas tinggi, menjadikan dirinya "bergaya kerajaan" karena terpengaruh masa kecilnya di rumah kerajaan Thembu, dan selama masa pemerintahannay sering dibanding-bandingkan dengan raja konstitusional. Dianggap sebagai "master citra dan penampilan", ia sangat pintar menampilkan dirinya saat difoto pers dan mulutnya sering mengeluarkan suara gigit.
Mandela adalah seorang nasionalis Afrika, posisi ideologi yang ia pegang terus sejak bergabung ANC, sekaligus menjadi "demokrat dan sosialis". Walaupun menampilkan diri dengan gaya otokratik dalam beberapa pidatonya, Mandela adalah penganut demokrasi dan akan mematuhi keputusan mayoritas bahkan jika ia sangat tidak setuju. Ia memegang keyakinan bahwa "keterlibatan, pertanggungjawaban, dan kebebasan berbicara" adalah dasar-dasar demokrasi, dan didorong oleh kepercayaan akan hak alami dan hak asasi manusia.
Sebagai seorang sosialis demokratik, Mandela "secara terbuka menentang kapitalisme, kepemilikan lahan swasta, dan kekuatan pihak berkantong tebal". Dipengaruhi Marxisme, selama revolusi Mandela menyerukan sosialisme ilmiah, meski ia menolak dicap komunis pada Pengadilan Pengkhianatan. Biografer David James Smith menduga ini tidak benar dan menyatakan bahwa Mandela "menganut komunisme dan komunis" pada akhir 1950-an dan awal 1960-an, walaupun ia adlaah "sesama petualang" alih-alih anggota partai. Di Piagam Kebebasan 1955, yang penyusunannya dibantu Mandela, isinya menuntut nasionalisasi bank, tambang emas, dan tanah, percaya hal ini diperlukan untuk menjamin distribusi kekayaan secara adil. Meski punya kepercayaan seperti ini, Mandela tidak menasionalisasikan apapun selama masa pemerintahannya, khawatir ia akan menakuti investor asing. Keputusan ini separuh dipengaruhi jatuhnya negara sosialis di Uni Soviet dan Blok Timur sepanjang awal 1990-an.
Mandela telah menikah tiga kali, menjadi ayah dari enam anak, memiliki 17 cucu per April 2013, dan cicit yang terus bertambah. Dianggap tidak demonstratif secara fisik dengan anak-anaknya, Mandela bisa saja bersikap keras dan menuntut terhadap mereka, namun justru lebih sayang kepada cucu-cucunya.
Pernikahan pertama Mandela adalah dengan Evelyn Ntoko Mase, yang berasal dari Transkei dan bertemu di Johannesburg sebelum menikah pada bulan Oktober 1944. Keduanya berpisah tahun 1957 setelah 13 tahun menikah, lalu bercerai akibat Mandela dituduh sering selingkuh dan tidak berada di rumah, setia dengan perjuangan revolusi, dan fakta bahwa Evelyn adalah anggota Saksi-Saksi Yehuwa, agama yang mewajibkan netralitas politik.
Keduanya dikaruniai dua putra, Madiba "Thembi" Thembekile (1946–1969) dan Makgatho Mandela (1950–2005), dan dua putri, keduanya bernama Makaziwe Mandela (known as Maki; lahir 1947 dan 1953). Putri pertama mereka meninggal pada usia sembilan bulan dan mereka memberi nama putri keduanya sama seperti itu sebagai bentuk penghormatan. Mase meninggal dunia tahun 2004 dan Mandela menghadiri pemakamannya. Putra Makgatho, Mandla Mandela, menjadi kepala dewan suku Mvezo pada tahun 2007.
Istri kedua Mandela, Winnie Madikizela-Mandela, juga berasal dari Transkei meski mereka juga bertemu di Johannesburg, tempat Winnie menjadi pekerja sosial berkulit hitam pertama di kota itu. Mereka dikaruniai dua putri, Zenani (Zeni), lahir 4 Februari 1958, dan Zindziswa (Zindzi) Mandela-Hlongwane, lahir 1960. Zindzi hanya berusia 18 bulan ketika ayahnya dikirim ke Pulau Robben. Winnie kelak merasa sangat hancur akibat percekcokan keluarga yang menyerupai kekacauan politik negara ini; saat suaminya menjalani hukuman penjara seumur hidup di Pulau Robben, ayahnya menjadi menteri pertanian di Transkei. Pernikahan ini berakhir dengan perpisahan (April 1992) dan perceraian (Maret 1996), diperparah oleh pengasingan politik. Mandela masih dipenjara ketika putrinya, Zenani, menikah tahun 1973 dengan Pangeran Thumbumuzi Dlamini, saudara Raja Mswati III dari Swaziland dan Ratu Mantfombi dari suku Zulu. Meski ia punya ingatan jelas tentang ayahnya, sejak usia empat sampai enam belas tahun, otoritas Afrika Selatan melarang ia menjenguknya. Bulan Juli 2012, Zenani ditunjuk sebagai duta besar untuk Argentina dan menjadi anak Mandela pertama yang memasuki kehidupan publik.
Mandela menikah kembali pada ulang tahunnya ke-80 tahun 1998 dengan Graça Machel ("née" Simbine), janda Samora Machel, mantan presiden Mozambik dan sekutu ANC yang tewas dalam kecelakaan pesawat 12 tahun sebelumnya.
Di Afrika Selatan, Mandela sering dipanggil dengan nama klan Xhosa-nya, Madiba.
Di South Africa, Mandela secara luas dianggap sebagai "bapak bangsa", dan "bapak pendiri demokrasi", dipandang sebagai "pembebas bangsa, sang penyelamat, Washington dan Lincoln digabung menjadi satu". Pada tahun 2004, Johannesburg memberikan Mandela kunci kota, dan pusat perbelanjaan Sandton Square diganti namanya menjadi Nelson Mandela Square setelah sebuah patung Mandela dipasang di sana. Tahun 2008, patung Mandela dipasang di Groot Drakenstein Correctional Centre, sebelumnya Penjara Victor Verster, dekat Cape Town, di titik tempat Mandela dibebaskan dari penjara.
Ia juga mendapat banyak pujian dari dunia internasional. Pada tahun 1993, ia menerima Hadiah Perdamaian Nobel bersama de Klerk. Bulan November 2009, Majelis Umum Perserikatan Bangsa-Bangsa menetapkan ulang tahun Mandela, 18 Juli, sebagai "Hari Mandela", yang menandakan kontribusinya untuk perjuangan antiapartheid. Peringatan ini meminta semua orang menyumbangkan 67 menit waktunya untuk menolong orang lain. Angka tersebut diambil dari 67 tahun masa keterlibatan Mandela dalam pergerakan antiapartheid.
Selain US Presidential Medal of Freedom, dan Order of Canada, ia merupakan orang hidup pertama yang mendapatkan status warga negara kehormatan Kanada. Setelah menjadi penerima terakhir Hadiah Perdamaian Lenin dari Uni Soviet, pada tahun 1990 ia menerima Bharat Ratna Award dari pemerintah India, dan tahun 1992 ia menerima Nishan-e-Pakistan dari Pakistan. Pada tahun 1992, ia dianugerahkan Atatürk Peace Award oleh Turki. Ia menolaknya karena waktu itu Turki melakukan serangkaian pelanggaran hak asasi manusia, namun akhirnya diterima Mandela tahun 1999. Elizabeth II menganugerahkan Mandela Bailiff Grand Cross of the Order of St. John dan Order of Merit.
Banyak artis yang mempersembahkan lagunya kepada Mandela. Salah satu lagu yang paling terkenal adalah "Free Nelson Mandela" dari The Special AKA tahun 1983, yang juga dinyanyikan Elvis Costello dan sama-sama terkenal. Stevie Wonder mendedikasikan Piala Oscar 1985 untuk lagu "I Just Called to Say I Love You"-nya kepada Mandela, sampai-sampai musiknya dilarang beredar oleh South African Broadcasting Corporation. Tahun 1985, album Youssou N'Dour "Nelson Mandela" adalah rilis pertama artis Senegal ini di Amerika Serikat. Artis-artis lain yang merilis lagu atau video sebagai penghormatan untuk Mandela meliputi Johnny Clegg, Hugh Masekela, Brenda Fassie, Beyond, Nickelback, Raffi, dan Ampie du Preez dan AB de Villiers.
Mandela telah ditampilkan di film dan televisi beberapa kali. Film tahun 1997, "Mandela and de Klerk", dibintangi Sidney Poitier yang berperan sebagai Mandela, sedangkan Dennis Haysbert memerankannya di "Goodbye Bafana" (2007). Dalam film televisi BBC tahun 2009, "Mrs Mandela", Nelson Mandela diperankan oleh David Harewood, dan Morgan Freeman memerankannya di "Invictus" (2009).