Nelson Mandela
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 3500 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 750000 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 750000 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