Van gevangene tot president
Met het aantreden van De Klerk als president van Zuid-Afrika kwamen er grote veranderingen in het bewind van de regering. De president begon eind 1989 een reeks gesprekken met Mandela en in februari 1990 werd het verbod op het ANC en andere politieke organisaties opgeheven. Mandela kwam op vrije voeten.
Op 11 februari 1990 verliet Mandela onder grote wereldwijde belangstelling de Victor Verster-gevangenis. Hij had op dat moment 27 jaar vastgezeten. Vrijwel onmiddellijk pakte hij zijn taak als vice-voorzitter van het ANC weer op.
Onderhandelingen
Onderhandelingen met de Nationale Partij verliepen stroef, omdat er onder meer binnen de politie en het leger nog veel weerstand bestond tegen de hervormingspolitiek. Ook de vaak gewelddadige strijd tussen de Zulu-beweging Inkatha en het ANC zorgde voor onrust.
Het ANC en de regering tekenden in augustus een verdrag waarin werd afgesproken dat het onderlinge geweld zou worden gestaakt. Het verdrag maakte echter geen einde aan het geweld van de politiemacht tegen ANC-aanhangers.
Winnie voor de rechter
Mandela's vrouw Winnie, die al een tijdje in opspraak was wegens de activiteiten eind jaren 80 van haar knokploeg, de zogenaamde Mandela United Football Club, moest begin 1991 terechtstaan. Ze zou schuldig zijn aan de ontvoering en mishandeling van vier jongetjes en verantwoordelijk zijn voor de dood van Stompie Seipei.
Ze werd slechts schuldig gevonden aan ontvoering. De straf van zes jaar werd in hoger beroep omgezet in een voorwaardelijke straf en een boete. Er bleven echter verdenkingen dat Winnie meer op haar kerfstok had. Mandela's steun aan Winnie leverde hem een deuk op in zijn imago.
Onderhandelen als voorzitter
Op de eerste jaarlijkse ANC-conferentie in juli 1991 werd Mandela tot voorzitter van het ANC gekozen. In de hierop volgende periode werd Mandela's tijd voor een groot deel in beslag genomen door overleg met de regering.
De onderhandelingen, onder de naam CODESA, waren aanvankelijk geen succes; Mandela en De Klerk oefenden openlijk felle kritiek uit op elkaar, de besprekingen werden zonder resultaat afgesloten en het geweld tussen politie en ANC-aanhang duurde voort. Vijf maanden later werd er begonnen met de CODESA 2-besprekingen, die opnieuw zonder resultaat werden afgesloten.
Het ANC besloot de druk op de regering op te voeren door stakingen, boycots en protestmarsen. Deze verliepen over het algemeen zonder geweld, maar de strijd tussen ANC en Inkatha eiste in deze periode opnieuw tientallen slachtoffers. De ANC-acties groeiden mede hierdoor in omvang, waarbij de roep om een einde aan het geweld steeds luider werd.
Successen
In september 1992 hervatten De Klerk en Mandela hun besprekingen, ditmaal met meer succes. De Klerk stelde een officieel onderzoek in naar het geweld en de rol van de politie hierin. Tevens werden er afspraken gemaakt over nieuwe verkiezingen en een nieuwe grondwet. In de maanden hierna nam het geweld in Zuid-Afrika langzaam maar zeker af.
Eind 1993 namen De Klerk en Mandela gezamenlijk de Nobelprijs voor de Vrede in ontvangst. Een jaar later verscheen Mandela's autobiografie 'Long Walk to Freedom', waarin hij onder meer zijn ervaringen als gevangene beschreef.
De eerste vrije verkiezingen in Zuid-Afrika, waarbij zowel blank als zwart naar de stembus gingen, werden gehouden op 26 april 1994. Het ANC werd de grote winnaar met 63 procent van de ruim 22 miljoen uitgebrachte stemmen. Op 10 mei werd Mandela beëdigd als president van Zuid-Afrika.