1918年7月18日にトランスカイのウムタタ近郊クヌ村で、テンブ人の首長の子として生まれる。
ウィトワーテルスランド大学法学部を卒業。在学中の1944年にアフリカ民族会議(ANC) に入党。その青年同盟を創設し青年同盟執行委員に就任して反アパルトヘイト運動に取組む。その後、1950年 ANC 青年同盟議長に就任する。
1952年8月にヨハネスバーグにてオリバータンボと共に弁護士事務所を開業する。その年の12月にANC副議長就任。1958年ウィニーと結婚。
1961年11月、ウムコント・ウェ・シズウェ（民族の槍）という軍事組織を作り、最初の司令官になる。それらの活動などで1962年8月に逮捕される。
1964年に国家反逆罪終身刑となりロベン島に収監される。1982年、ケープタウン郊外のポルスモア刑務所に移監。
1989年12月にデクラーク大統領と会談。
1990年2月11日に釈放される。釈放後、ANC 副議長に就任する。当時の大統領デクラークとの予備会談に ANC 代表として出席。
1990年10月27日 ANC 代表団を率いて来日する(11月1日まで)。1991年ANC議長に就任。デクラークと協力して全人種代表が参加した民主南アフリカ会議を二度開き、さらに多党交渉フォーラムを開いた。暫定政府、暫定憲法を作成。
1992年4月13日、ウィニー夫人との離婚を表明。
1993年12月10日にデクラークとともにノーベル平和賞受賞。
1994年4月に南ア史上初の全人種参加選挙が実施された。ANC は勝利し、マンデラは大統領に就任した。暫定憲法の権力分与条項に基づき国民党、インカタ自由党と連立政権をたて、国民統合政府を樹立した。マンデラは民族和解・協調を呼びかけ、アパルトヘイト体制下での白人・黒人との対立や格差の是正、黒人間の対立の解消、経済不況からの回復として復興開発計画 (RDP) を公表した。
1996年3月19日にウィニーとの離婚が成立。
1997年12月の ANC 党大会でマンデラは、議長の座を副大統領のターボ・ムベキに譲る。
1998年7月18日にグラサ・マシェル夫人と結婚 。1999年2月5日、国会で最後の演説をした。同年行われた総選挙を機に政界から引退した。
2000年1月19日に国連安全保障理事会で初演説した。