לאחר טבח שארפוויל ב־1960, הוצא ה־ANC אל מחוץ לחוק בדרום אפריקה, ומנדלה נעצר בגין השתתפות במחאות אלימות וביצוע מעשי טרור. הוא הוחזק במעצר עד 1961. לאחר שחרורו, היה ברור שהמדיניות של הקונגרס, לפיה יש לחתור בדרכי שלום למדינה שוויונית שלא תתבסס על מוצא גזעי, לא השיגה את התוצאות המקוות. נוכח התגובה האלימה של השלטון והטלת העונשים על השחורים המוחים, החליט הקונגרס לעבור למאבק אלים בדרכי טרור.
אחד הגורמים שהשפיעו על מעבר הקונגרס לפעילות אלימה היה תגובות הציבור למאבק הלא אלים. היה ברור שהתומכים במדיניות אי האלימות החלו לאבד את אמונם בגישה זו, ופנו לדרכים הכוללות שימוש בטרור. בשלב זה הציבור השחור שתמך ברעיונותיו של מנדלה התקומם נגד פעילותו של הקונגרס בטענה שאינו פועל בצורה נכונה נגד תגובות השלטון הלבן, שנועדו לדכא את האוכלוסייה השחורה באמצעות אלימות וטרור, ולכן תגובה לא אלימה לא הייתה פתרון נכון למתרחש. תגובות השלטון למחאות הלא אלימות של מנדלה היוו גורם נוסף להחלטה למעבר למחאה אלימה כלפי השלטון הלבן והוקמה למפלגה זרוע צבאית. לאחר טבח שארפוויל הוצאו ה-PAC וה-ANC מחוץ לחוק ודוכאו על ידי השלטון במדינה. בנוסף, נאסרה פעילותם של איגודים מקצועיים של הציבור השחור. עקב החקיקות ופעולות הדיכוי נוצר בקרב האוכלוסייה השחורה משבר כלכלי חמור ותסכול רב, והדרך לפתור אותו הייתה להחיות את תנועות המאבק נגד האפרטהייד.
טענה של הקונגרס שהוצגה במשפט נגד הארגון:
בעקבות הלך רוח הציבור עבר נלסון מנדלה לפעילות אלימה נגד השלטון. לטענתו זוהי האפשרות היחידה שנותרה כדי לשנות את גורל האוכלוסייה השחורה במדינה.
שמו של הארגון הצבאי החדש שקם היה אומקונטו (MK) וסמלו היה חנית. בראש הארגון עמדו מנדלה, וולטר סיסולו וג'ו סלובו, אשר תמכו גם הם באופן פעיל בהתנגדות למדיניות האפרטהייד. האסטרטגיה של הזרוע הצבאית הייתה לערוך פשיטות על מתקנים צבאיים של השלטון במדינה, תחנות כוח, קווי טלפון וצירי תחבורה וזאת לא רק על מנת לפגוע ביכולת הצבאית של המדינה, אלא גם להפחיד את תומכי המפלגה הלאומית ולהחליש את הכלכלה במדינה. הארגון רצה לצמצם את הפגיעות בנפש, אך הבהיר שאם מעשי החבלה לא יביאו לביטול מדיניות האפרטהייד, השלב הבא יהיה מעבר לדרכי טרור ולוחמה. הזרוע הצבאית ערכה אימונים צבאיים והכשרות במדינות שונות ברחבי היבשת ואף באירופה במטרה להכשיר את תומכיה ומפקדיה לפעולות אלימות נגד השלטון במדינה. הלוחמים ב-MK עברו אימוני ירי ברובים ובאקדחים, לימוד חבלה וירי במרגמה, הכנת פצצות ומוקשים ומסעות ניווט עם נשק בזמן קצוב.
מנדלה ניהל בעצמו את ההגנה במשפטו. בנאומיו הצהיר כי הוא מוכן למות כדי לקדם את מטרתו. בנובמבר 1962 הורשע ונידון למאסר של חמש שנים. באותה עת הוכר על ידי אמנסטי אינטרנשיונל כאסיר מצפון.
ב-1963 פשטה המשטרה על חוות ליליסליף שהייתה בבעלותו של הפעיל היהודי נגד האפרטהייד ארתור גולדרייך, וחשפה מסמכים שהצביעו על מעורבותו של מנדלה בפעולות שונות. יחד עם גולדרייך נתפס פעיל יהודי נוסף, דניס גולדברג. כתוצאה מכך הוגש נגדו כתב אישום נוסף, והוא הואשם בפעילות חבלנית ובקשירת קשר נגד השלטון. משפטו התנהל בפרטוריה ונודע כמשפט ריבוניה (Rivonia Trial). ב-11 ביוני 1964 הורשע, ונדון למאסר עולם, לאחר שהשופט דחה את דרישת התביעה לעונש מוות. המשפט גונה על ידי מועצת הביטחון של האו"ם.
מנדלה היה כלוא בבתי כלא שונים של דרום אפריקה במשך 27 שנים, מתוכן 18 שנים, עד מרץ 1982, ברובן איילנד. יחד עם שלושה מנהיגים אחרים של הקונגרס הלאומי האפריקאי הועבר מנדלה ביום 31 במרץ 1982 לכלא פולסמור (Pollsmoor) באחד מפרווריה הדרומיים של קייפטאון, ובו ריצה מנדלה את עונש המאסר עד סוף שנת 1988. בתחילת דצמבר 1988 הועבר מנדלה לבית הסוהר ויקטור פרסטר (Victor Verster) ליד העיר פארל שבדרך היין. את צעדיו הראשונים לעבר החירות עשה מנדלה ביום 11 בפברואר 1990 מבית סוהר זה. בכניסה לבית הסוהר מוצב כיום פסל דיוקן של מנדלה, על בסיס צילום שצולם בעת יציאתו מבית הסוהר.
במהלך תקופת מאסרו הפך מנדלה לסמל המאבק באפרטהייד, שמו התפרסם בעולם כולו, והחל מאבק בינלאומי לשחררו. בתקופה האחרונה של מאסרו החל מנדלה לקיים מגעים חשאיים עם אישי ממשל בכירים, ובהם הנשיא פרדריק וילם דה קלרק. מנדלה שוחרר מהכלא ב־11 בפברואר 1990, לאחר שהוא וחבריו ל־ANC הסכימו להשעות את המאבק המזוין ולקיים משא ומתן עם השלטון.
לאחר שחרורו.
מנדלה ודה קלרק הובילו את דרום אפריקה לפירוק משטר ההפרדה הגזעית ולעריכתן של בחירות דמוקרטיות אמיתיות ראשונות ב־1994, שבהן הותר לראשונה לאזרחים שחורים ולצבעוניים (בני תערובת) להצביע. על פעילותם זו זכו מנדלה ודה קלרק בשנת 1993 בפרס נובל לשלום.
בבחירות שנערכו בין 26 ל-29 באפריל 1994 זכה ה־ANC לרוב בפרלמנט, אולם רוב קטן משני שלישים מהחברים הדרוש לשנות את החוקה. ב־9 במאי בחר בקייפטאון הפרלמנט החדש במנדלה לנשיאה השחור הראשון של דרום אפריקה, כאשר הנשיא היוצא דה קלרק נבחר לסגנו. ההשבעה נערכה למחרת בפרטוריה בהשתתפות מנהיגים רבים מהעולם, בהם סגן נשיא ארצות הברית אל גור, מזכ"ל האו"ם בוטרוס בוטרוס ראלי ומנהיג קובה פידל קסטרו.
אחת מפעולותיו הראשונות כנשיא הייתה הקמת ועדת האמת והפיוס בראשות חתן פרס נובל לשלום דזמונד טוטו, שחקרה את עוולות תקופת האפרטהייד הן מצד השלטון הלבן והן מצד ארגוני ההתנגדות השחורים, תוך מתן חנינה למי שהודה בפשעיו. תקופת נשיאותו הוקדשה להקמת חברה שוויונית וצודקת, ברוח של איחוד לאומי ופיוס בין הקבוצות האתניות השונות במדינה. בחודש יוני 1999 פרש מהפוליטיקה, והתגורר באזור שבו נולד, קונו, שבחבל טרנסקאי.
לאחר פרישתו מהנשיאות ב־1999 היה מנדלה מעורב במספר רב של ארגונים חברתיים ובארגוני זכויות אדם. הוא אף זכה במספר רב של תוארי כבוד מממשלות שונות על פעילותו הפוליטית והחברתית לאורך השנים. ב־2003 נשא מנדלה מספר נאומים מעוררי מחלוקת, בהם תקף את מדיניות החוץ של ג'ורג' בוש.
ביוני 2004, בגיל 85, הודיע מנדלה כי הוא פורש מהחיים הציבוריים. בשנותיו האחרונות הידרדרה בריאותו, ולדבריו רצה ליהנות מהזמן עם משפחתו ככל שבריאותו תרשה זאת. למעשה, היוצא מן הכלל היחיד היה התחייבותו למאבק נגד האיידס. ביולי 2004 הוא טס לבנגקוק כדי לשאת דברים בוועידת האיידס הבינלאומית. במהלך ינואר 2005 הודיע מנדלה כי בנו אף הוא נפטר מאיידס. הפרסום נועד להגברת המודעות למחלה ולשבירת הטאבו המתלווה אליה. בשנת 2010 השתתף מנדלה בטקס נעילת משחקי המונדיאל שנערך בדרום אפריקה, באחת מהופעותיו הציבוריות האחרונות.
ב-2008 הוציאה ארצות הברית את מנדלה מרשימת הטרוריסטים בה נכלל כאחד ממנהיגי ה-ANC, שמנעה ממנו כניסה למדינה.
יחסו לסכסוך הישראלי-פלסטיני.
מנדלה טען כי הוא "מבין היטב מדוע ישראל כבשה אדמות אלו (יהודה ושומרון). הייתה מלחמה." אך מנגד התנגד לכיבושם המתמשך ואף הצהיר בביקור בעזה כי "אין טעם לדבר על שלום כל עוד היא (ישראל) עדיין מחזיקה בשטחים". הוא האמין שערפאת רצה בשלום עם ישראל וראה בו דמות הירואית. עם פטירת ערפאת ספד לו ואמר כי "ערפאת היה אייקון ואחד הטובים בעולם". באפריל 2016 נחנכה ברמאללה ככר על שמו של מנדלה ובמרכזה פסל בדמותו. את הפסל שגובהו 6 מטרים מימנה עיריית יוהנסבורג.
מנגד, מנדלה סיפר שספרו של מנחם בגין "המרד" היווה מקור השראה עבורו והוא תיאר את דוד בן-גוריון כמנהיג משכמו ומעלה. הוא הביע סימפתיה לעם היהודי ולמדינת ישראל, ואמר כי "למרות הסבל והקשיים האדירים שפקדו את העם היהודי ומדינת ישראל לאורך השנים, תמיד שמתם דגש מיוחד על החינוך וההשכלה, וזהו סוד הצלחתכם. אני קורא לבני עמי לראות זאת כמודל לחיקוי".
פטירתו.
במהלך שנת 2013 אושפז מנדלה מספר פעמים בשל זיהום בריאות. ב-5 בדצמבר 2013 הוא נפטר בביתו ביוהנסבורג.
ב-10 בדצמבר 2013 נערך באצטדיון סוקר סיטי ביוהנסבורג טקס אשכבה למנדלה, בו נכחו מנהיגים ממדינות רבות, בהם נשיא ארצות הברית ברק אובמה. ב-15 בדצמבר הוא הובא לקבורה בטקס ממלכתי בכפר ילדותו קונו שבפרובינציית הכף המזרחי.
הוקרה.
מנדלה נחשב ממנהיגי המאבק נגד משטר האפרטהייד ונבחר על ידי תושבי דרום אפריקה כ"אבי האומה". מנדלה היה ידוע כאדם מוערך בעולם וזכה בפרסים רבים, כמו: פרס נובל לשלום לשנת 1993, פרס סחרוב לחופש המחשבה לשנת 1988, מסדר ההצטיינות הבריטי, מדליית החירות הנשיאותית ומדליית הזהב של הקונגרס של ארצות הברית, ואף נבחר לאיש השנה של המגזין טיים.
אודות מנדלה נכתבו ביוגרפיות רבות, ואף הופקו מספר סרטים על חייו. אחד מראשי המאבק הבינלאומי למענו היה העיתונאי הליברלי ריצ'רד סטנגל, כיום העורך הראשי של טיים מגזין. סטנגל אף היה סופר הצללים שכתב יחד עם מנדלה את האוטוביוגרפיה שלו, שיצאה לאור ב-1993 בהוצאת ליטל, בראון - "Long Walk to Freedom" (הספר תורגם גם לעברית ויצא לאור בישראל ב-1994), שעובד לסרט קולנוע בשם "ארוכה הדרך לחירות", בכיכובם של אידריס אלבה ונעמי האריס. ב-1996 היה סטנגל מפיק שותף של הסרט הדוקומנטרי "מנדלה", שהיה מועמד לפרס אוסקר.
בשנת 2009 יצא לאקרנים הסרט "אינוויקטוס", המתאר את ראשית תקופת נשיאותו של מנדלה, שגולם בידי השחקן מורגן פרימן ובוים בידי קלינט איסטווד. בנובמבר 2012 הנציחה הממשלה את דמותו על שטרות הראנד הדרום-אפריקאי.
בשנת 2017 הופקה סדרת טלוויזיה ביוגרפית על חייו בשם "מדיבה", בכיכובו של לורנס פישבורן.
חיים אישיים.