การเลือกตั้งแบบหลากชนชาติครั้งแรกในแอฟริกาใต้โดยที่พลเมืองทุกคนมีสิทธิเสียงเท่ากัน เกิดขึ้นในวันที่ 27 เมษายน พ.ศ. 2537 พรรคเอเอ็นซีชนะการเลือกตั้งด้วยคะแนนเสียง 62% และแมนเดลาในฐานะผู้นำพรรคเอเอ็นซีได้เข้าพิธีรับตำแหน่งเป็นประธานาธิบดีในวันที่ 10 พฤษภาคม พ.ศ. 2537 เป็นประธานาธิบดีผิวดำคนแรกของประเทศ โดยมี เดอ แกลร์ก จากพรรคชาตินิยม และทาโบ อึมแบกี เป็นรองประธานาธิบดีทั้งสองคนในการตั้งรัฐบาลผสมแห่งชาติ[67] เขาเป็นประธานาธิบดีตั้งแต่เดือนพฤษภาคม พ.ศ. 2537 จนถึงเดือนมิถุนายน พ.ศ. 2542 ได้เปลี่ยนแปลงกฎหมายเกี่ยวกับการเหยียดสีผิวหรือชนกลุ่มน้อยต่าง ๆ และได้รับความยกย่องจากนานาชาติสำหรับการอุทิศตนเพื่อการประสานไมตรีทั้งในระดับชาติและระดับนานาชาติ[68] แมนเดลาให้การสนับสนุนแก่ชาวแอฟริกันผิวดำให้เข้าร่วมและสนับสนุนทีมสปริงบอกส์ ซึ่งเป็นทีมชาติรักบี้ของแอฟริกาใต้ ในโอกาสที่ประเทศแอฟริกาใต้ได้เป็นเจ้าภาพจัดการแข่งขันรักบี้โลกในปี พ.ศ. 2538[69] หลังจากทีมสปริงบอกส์สามารถเอาชนะทีมรักบี้จากนิวซีแลนด์ได้ในการแข่งขันรอบชิงชนะเลิศ แมนเดลาเป็นผู้มอบถ้วยรางวัลให้แก่กัปตันทีม ฟรังซัวส์ ปีเยนาร์ ชาวแอฟริกันซึ่งสวมเสื้อทีมสปริงบอกส์กับตัวเลข 6 บนหลังซึ่งเป็นหมายเลขประจำตัวของเขา ภาพนี้เผยแพร่ไปทั่วไปในฐานะก้าวย่างอันสำคัญแห่งการสมานฉันท์ระหว่างชนผิวขาวและผิวดำในแอฟริกาใต้[70]

หลังจากที่เป็นประธานาธิบดี สัญลักษณ์สำคัญอย่างหนึ่งของแมนเดลาคือการสวมเสื้อบาติก ที่เรียกกันว่า "เสื้อมาดิบา" แม้กระทั่งในงานพิธีการต่าง ๆ[71] ในการปฏิบัติการทางทหารของแอฟริกาใต้ครั้งแรกหลังจากยุติการแบ่งแยกสีผิว แมนเดลาสั่งการให้กองทัพเคลื่อนเข้าไปเลโซโท ในเดือนกันยายน พ.ศ. 2541 เพื่อช่วยปกป้องรัฐบาลของนายกรัฐมนตรี Pakalitha Mosisili หลังจากที่มีการเลือกตั้งอันวุ่นวายและเกิดการประจันหน้ากันระหว่างฝ่ายตรงข้ามกับฝ่ายรัฐบาลที่ไร้เสถียรภาพ[72] นักวิจารณ์จำนวนมากรวมถึงนักรณรงค์ต่อต้านโรคเอดส์ เช่น เอ็ดวิน คาเมรอน ได้วิพากษ์วิจารณ์แมนเดลาอย่างมากในความไร้ประสิทธิภาพของรัฐบาลของเขากับการรับมือวิกฤตการณ์โรคเอดส์[73][74] หลังจากที่เขาเกษียณแล้ว แมนเดลายอมรับว่าเขาทำให้ประเทศต้องผิดหวังเนื่องจากมิได้ให้ความสำคัญกับการระบาดของเชื้อเอชไอวีและโรคเอดส์เท่าที่ควร[75][76] นับแต่นั้นแมนเดลาได้ขึ้นพูดในหลายโอกาสเพื่อรณรงค์ต่อต้านการแพร่กระจายของโรคเอดส์[77][78]

การฟื้นฟูเศรษฐกิจ

หลังจากเสร็จสิ้นการเลือกตั้งปี พ.ศ. 2537 รัฐบาลได้ริเริ่มโครงการพัฒนาและปรับปรุงโครงสร้างพื้นฐาน (Reconstruction and Development Program; RDP) เพื่อสร้างความเสมอภาคทางเศรษฐกิจแก่ประชาชนหลังสิ้นสุดยุคของอาพาร์ไทด์ ซึ่งเคยมีแต่ความลำบากยากแค้นและไม่ได้รับการเหลียวแล ทำให้เกิดปัญหาต่อสิ่งแวดล้อมในระดับมหภาคด้วย[79] ขนาดของโครงการนี้อาจเทียบได้กับ "New Deal" ของรัฐบาลสหรัฐอเมริกาเมื่อคราววิกฤตเศรษฐกิจตกต่ำครั้งใหญ่ โครงการนี้ได้รับการสนับสนุนจากองค์กรทางการเมืองทุกองค์กร[80]

ระหว่าง พ.ศ. 2537 ถึงต้นปี พ.ศ. 2544 รัฐบาลแอฟริกาใต้ได้ให้ความช่วยเหลือในการสร้างบ้านอยู่อาศัยต้นทุนต่ำมากกว่า 1.1 ล้านหลัง เพื่อรองรับชาวแอฟริกาใต้ 5 ล้านคนจากจำนวนคนยากจน 12.5 ล้านคน[81] ระหว่าง พ.ศ. 2537-2543 ชาวบ้านกว่า 4.9 ล้านคนที่อาศัยอยู่ตามท้องถิ่นสามารถเข้าถึงแหล่งน้ำดื่มสะอาด อีกกว่า 1.75 ล้านครัวเรือนมีไฟฟ้าใช้ สัดส่วนครอบครัวชนบทที่เข้าถึงระบบไฟฟ้าเพิ่มขึ้นจาก 12% เป็น 42%[81] ปี พ.ศ. 2542 มีครอบครัวที่ได้รับประโยชน์จากการจัดสรรที่ทำกิน 3550 ตารางกิโลเมตร จำนวน 39,000 ครอบครัว เมื่อเทียบกับวาระ 4 ปีของรัฐบาล ประชาชนได้รับที่ทำกินรวม 250,000 คน[81] จากเดือนเมษายน พ.ศ. 2537 ถึงปลายปี 2541 มีคลินิกใหม่ 500 แห่งเพื่อให้บริการสาธารณสุขแก่พลเมือง 5 ล้านคน พร้อมโครงการฉีดวัคซีนป้องกันโรคโปลิโอและตับอักเสบ เริ่มขึ้นในปี พ.ศ. 2541 ซึ่งช่วยให้เด็ก ๆ กว่า 8 ล้านคนมีชีวิตขึ้นมาสู่ระดับมาตรฐานภายในเวลา 2 ปี[81] มีโครงการก่อสร้างถนนและระบบระบายน้ำ ช่วยสร้างงานแก่ประชาชน 240,000 คนตลอดเวลา 5 ปี[81] อย่างไรก็ดี โครงการ RDP ก็ถูกวิพากษ์วิจารณ์มากว่า กว่า 30% ของบ้านต้นทุนต่ำเหล่านั้นสร้างต่ำกว่ามาตรฐาน[81] ระบบจ่ายน้ำต้องขึ้นกับแม่น้ำและเขื่อนมากมาย[82] และโครงการเว้นการเก็บเงินจากชาวชนบทผู้ยากจนก็ใช้เงินสูงมาก[81] การจัดสรรที่ทำกินสามารถแจกจ่ายที่ดินออกไปได้จริงเพียง 1% และระบบสาธารณสุขไม่มีความสามารถพอจะต่อสู้กับการระบาดของโรคเอดส์ ซึ่งทำให้คุณภาพชีวิตเฉลี่ยของชาวแอฟริกาใต้ลดต่ำลงจาก 64.1% เป็น 53.2% ตั้งแต่ปี 2538 ถึง 2541[81]

การไต่สวนคดีล็อกเคอร์บี

ประธานาธิบดีแมนเดลามีความสนใจอย่างยิ่งที่จะช่วยไกล่เกลี่ยข้อพิพาทอันยาวนานระหว่าง กัดดาฟี แห่งลิเบีย กับสหรัฐอเมริกาและอังกฤษ โดยการร้องขอให้มีการไต่สวนผู้ต้องหาชาวลิเบีย 2 คนซึ่งถูกฟ้องร้องเมื่อเดือนพฤศจิกายน พ.ศ. 2534 ในข้อหาวางระเบิดสายการบิน แพน แอม เที่ยวบิน 103 ที่ระเบิดที่เมืองล็อกเคอร์บีในสกอตแลนด์ เมื่อวันที่ 21 ธันวาคม 2531 ซึ่งทำให้มีผู้เสียชีวิตถึง 270 คน[83] ช่วงต้นปี พ.ศ. 2535 แมนเดลาได้แจ้งข้อเสนออย่างเป็นทางการต่อประธานาธิบดี จอร์จ เอช. ดับเบิลยู. บุช เพื่อขอให้ชาวลิเบียทั้งสองได้รับการไต่สวนในประเทศที่สาม บุชตอบรับข้อเสนอนี้อย่างยินดี เช่นกันกับประธานาธิบดีฟร็องซัว มีแตร็อง แห่งฝรั่งเศส และสมเด็จพระราชาธิบดีควน การ์โลส ที่ 1 แห่งสเปน[84] เดือนพฤศจิกายน พ.ศ. 2537 - หกเดือนหลังจากเขาได้รับเลือกเป็นประธานาธิบดี - แมนเดลาได้ยื่นข้อเสนออย่างเป็นทางการว่า ประเทศแอฟริกาใต้ควรเป็นผู้จัดการไต่สวนคดีวางระเบิดสายการบิน แพน แอม 103[85]

ทว่านายกรัฐมนตรีอังกฤษ จอห์น เมเจอร์ ปฏิเสธข้อเสนอนี้โดยกล่าวว่ารัฐบาลอังกฤษไม่มีความมั่นใจในการไต่สวนของศาลต่างประเทศ[86] เวลาล่วงผ่านไปอีก 3 ปีจนกระทั่งแมนเดลายื่นข้อเสนออีกครั้งต่อผู้สืบตำแหน่งนายกรัฐมนตรีอังกฤษคนใหม่ คือ โทนี แบลร์ ในคราวที่ท่านประธานาธิบดีไปเยือนลอนดอน ในเดือนกรกฎาคม พ.ศ. 2540 ถัดมาในปีเดียวกัน ในที่ประชุม การประชุมกลุ่มประเทศเครือจักรภพ (Commonwealth Heads of Government Meeting หรือ CHOGM) ที่เมืองเอดินบะระ ซึ่งจัดขึ้นในเดือนตุลาคม พ.ศ. 2540 แมนเดลาก็กล่าวเตือนว่า :

ประเทศหนึ่งประเทศใดไม่ควรเป็นทั้งผู้ร้องทุกข์ อัยการ และผู้พิพากษาในคราวเดียว

ข้อสรุปอันประนีประนอมได้ความว่าการไต่สวนจะจัดขึ้นที่ Camp Zeist ในประเทศเนเธอร์แลนด์ ซึ่งใช้กฎหมายของสก๊อต ประธานาธิบดีแมนเดลาเริ่มการเจรจากับนายพลกัดดาฟีให้ส่งมอบตัวผู้ต้องหา (เมกราฮี กับฟีห์มาห์) ในเดือนเมษายน พ.ศ. 2542[87] เมื่อสิ้นสุดการไต่สวนอันยาวนานกว่า 9 เดือน มีการประกาศคำตัดสินของคณะลูกขุนเมื่อวันที่ 31 มกราคม พ.ศ. 2544 ฟีห์มาห์ไม่มีความผิด แต่เมกราฮีมีความผิดและต้องโทษจำคุก 27 ปีในเรือนจำของสก๊อตแลนด์ คำอุทธรณ์ครั้งแรกของเมกราฮีถูกปฏิเสธเมื่อเดือนมีนาคม พ.ศ. 2545 อดีตประธานาธิบดีแมนเดลาได้เดินทางไปเยี่ยมเขาที่เรือนจำบาร์ลินนี เมื่อวันที่ 10 มิถุนายน 2545

"เมกราฮีโดดเดี่ยวอย่างแท้จริง" แมนเดลากล่าวในการแถลงข่าวสั้น ๆ ที่ห้องเยี่ยมของเรือนจำ "เขาไม่สามารถคุยกับใครได้เลย มันเป็นการประหารทางจิตใจแท้ ๆ เมื่อคน ๆ หนึ่งจะต้องใช้ชีวิตของเขาในการรับโทษอันยาวนานโดยอยู่เพียงลำพังคนเดียว คงจะดีกว่านี้หากเขาได้รับอนุญาตให้ย้ายไปอยู่ในประเทศมุสลิม มีประเทศมุสลิมมากมายที่ทางฝั่งตะวันตกเชื่อใจได้ ครอบครัวของเขาจะได้ไปเยี่ยมเขาได้บ้างหากเขาอยู่ในประเทศ เช่น โมร็อกโก ตูนิเซีย หรืออียิปต์"[88]

ในเวลาต่อมา เมกราฮีได้ย้ายไปยังเรือนจำกรีน็อค และไม่ต้องถูกขังเดี่ยวอีกต่อไป[89] วันที่ 28 มิถุนายน พ.ศ. 2550 คณะกรรมการทบทวนคดีอาชญากรรมแห่งสก๊อตแลนด์ (Scottish Criminal Cases Review Commission) ได้มีข้อสรุปว่า หลังจากทบทวนการตัดสินโทษของเมกราฮีเป็นเวลา 3 ปี เชื่อได้ว่ามีการตัดสินลงโทษแก่ผู้มิได้กระทำความผิดจริง อ้างตามคำอุทธรณ์ครั้งที่ 2 จากศาลอุทธรณ์คดีอาชญากรรม[90]