1982 m. kovo 31 d. jis buvo perkeltas į Polsmoro įkalinimo įstaigą, o 1988 m. gruodžio 7 d. (ar 9 d.) – į vadinamąjį Victoro Versterio kalėjimą – privačių namų kompleksą, naudotą menką grėsmę keliantiems politiniams kaliniams laikyti.

Paskutiniais savo įkalinimo metais Nelsonas itin dažnai susitikdavo pabendrauti su Pietų Afrikos apartheido režimo atstovais. Šiuose pokalbiuose neretai iškildavo ne tik N.R.Mandelos paleidimo į laisvę, bet ir Pietų Afrikos Respublikos politinės ateities klausimai, mat tuo metu žymusis kalinys jau buvo tapęs mitologiniu personažu, garbinamu tiek Afrikoje, tiek kituose žemynuose.

Tarptautinis, politinis, diplomatinis ir ekonominis spaudimas apartheido režimui buvo prasidėjęs dar iki 1963 m. spalio 9 d. – 1964 m. birželio 12 d. teismo, tačiau po N.R.Mandelos įkalinimo priešiškumas rasinės segregacijos politikai tik dar labiau išaugo, o jam išreikšti naudotos įvairaus pobūdžio priemonės (nuo žmogžudysčių ir teroro aktų iki taikaus protesto).

1966 m. rugsėjo 6 d. buvo nužudytas Hendrikas Frenschas Verwoerdas (1901–1966). Šis Pietų Afrikos ministras pirmininkas iki šiol yra vertinamas itin kontroversiškai, mat daug prisidėjo prie praktinio ir teorinio apartheido santvarkos įtvirtinimo, o valdydamas šalį nevengė autoritarinio pobūdžio metodų.

1976 m. birželio 16 d. Soveto mieste juodaodžiams moksleiviams pradėjus protesto akciją, vėl buvo pralietas kraujas, nes jėgos struktūrų atstovai atidengė ugnį. XX a. 9-ame dešimtmetyje viena svarbiausių kovos su apartheidu jėgų tapo Jungtinis demokratinis frontas (United Democratic Front). Šita skirtingų rasių ir socialinių sluoksnių žmones vienijanti organizacija pasirinko taikaus protesto kelią.

Laikui bėgant, JAV ir Vakaruose apartheido kritika tapo tokiu pat madingu gero tono ženklu, kokiu mūsų dienomis yra kova su klimato kaita ar karas su "netikromis naujienomis" (fake news).

Skirtingai nei Sovietų Sąjunga, Pietų Afrikos apartheido režimas neturėjo nei rimtų imperialistinių ambicijų, nei šimtmečių patirtį sukaupusios slaptosios politinės policijos, nei daugumai patrauklios idėjos, nei galingos lobistų ir naudingųjų idiotų armijos, galinčios stumti autoritarinio pobūdžio santvarką kitiems pro visus galus.

Itin didelį priešiškumą Pietų Afrikos rasinės segregacijos politikai rodė pramogų pasaulio įžymybės, tad nesunku nuspėti, jog, tvyrant išoriniam spaudimui bei vidiniam chaosui, apartheido režimo pamatai ėmė braškėti.

Pirmosios politinio pavasario kregždės į Pietų Afriką atskrido prezidento pareigas einant Pieteriui Willemui Bothai (1916–2006). Nors šis politikas vis dar griežtai laikėsi rasinės segregacijos krypties, jo dėka buvo padaryti pirmieji paviršutiniški pokyčiai (pavyzdžiui, legalizuotos skirtingų rasių atstovų santuokos ir užmegzti kontaktai su žymiuoju kaliniu N.R.Mandela).

1989 m. P.W.Bothai iškilo rimtų sveikatos problemų ir dar tų pačių metų vasarį jis pasitraukė iš Nacionalinės partijos lyderio pareigų, o 1989 m. rugpjūtį prezidento poste jį pakeitė Frederikas Willemas de Klerkas (1936). Atėjus į valdžią šiam politikui, apartheido režimo ir N.R.Mandelos pasimatymai tapo dar dažnesni, o pokalbiai – turiningesni, ir 1990 m. vasario 11 d. jis iškilmingai ir prašmatniai buvo paleistas į laisvę.

Tuo metu tiek vakariečių, tiek vietinių juodaodžių akyse N.R.Mandela jau buvo tapęs kone gyvu dievu, kurio išėjimas iš kalėjimo daug kam simbolizavo naujo etapo Pietų Afrikos istorijoje pradžią.

Prasidėjus deryboms dėl Pietų Afrikos ateities, N.R.Mandela su savo bendražygiais ėmė reikalauti mažoritarinės rinkimų sistemos, kuri leistų gyventojų daugumą sudarantiems juodaodžiams dominuoti politikoje.

Savo ruožtu F.W. de Klerko atstovaujama baltųjų mažuma taip pat nenorėjo nusileisti, tad po šypsenomis ir mandagiais spaudoje deklaruojamais lozungais paslėptos derybos buvo išties sunkios, o įvairūs išoriniai veiksniai jas ne kartą buvo privedę ties žlugimo riba.

Dar 1989 m. rudenį Pietų Afrikos spaudoje apsireiškė žmogus Dirko Coetzees (1945–2013) pavarde. Šis veikėjas prieš apartheidą pasisakantiems leidiniams tvirtino ne vienerius metus vadovavęs specialiam policijos padaliniui, kuris režimo užsakymu eliminuodavo kritikus. 1992 m. Pietų Afrikos policija šitą istoriją išspausdinusius laikraščius padavė į teismą, kurį sėkmingai pralaimėjo.

Beveik tuo pat metu F.W. de Klerkui teko susidurti su baltųjų ekstremistų spaudimu. Buvo reikalaujama referendumo, kuris atsakytų, ar Pietų Afrikos baltieji pritaria naujai F.W. de Klerko politikai. 1992 m. kovo 17 d. vykusio balsavimo metu didžioji dalis baltųjų atsakė "taip".

Tų pačių metų birželio 17 d. zulų aktyvistai atėjo į Afrikos nacionalinio kongreso pasekėjų gyvenvietę Boipatonge ir nužudė 45 žmones, mat vykstant deryboms prasidėjo keistas konfliktas tarp zulų partijos ir N.R.Mandelos vadovaujamo Afrikos nacionalinio kongreso. Vėliau, rugsėjo 7 d., Bišo mieste įvyko dar vienos žudynės, kurias šį kartą įvykdė valdančiojo režimo atstovai.

Nepaisant vis iškylančių kliūčių, grasinančių sužlugdyti tiek derybas, tiek sudirginti prie pilietinio karo ribos stovinčią šalį, N.R.Mandelos ir F.W. de Klerko atstovaujamoms jėgoms pavyko pasiekti kompromisą. 1993 m. gruodžio 10 d. šios pastangos buvo įvertintos bendra Nobelio taikos premija.

Daug kas tokį sprendimą tuo metu vertino kontroversiškai, mat buvo tikima, kad premijos nusipelnė vien N.R.Mandela. Taip pat aiškinta, jog F.W. de Klerkas buvo kilęs iš apartheido baltųjų elito sluoksnio ir pats jaunystėje palaikė rasinės segregacijos politiką.

Sakoma, kad N.R.Mandela nebuvo patenkintas šiuo Nobelio teikėjų sprendimu.