曼德拉和他的共同被告被从比勒陀利亚转移到罗本岛的监狱，并在那儿连续关押了18年。曼德拉与B区的非政治囚犯分隔开，被关押在一个只有8x7英尺（即长2.4m宽2.1m）的潮湿的水泥牢房里，里面放了一张草垫给他睡觉。经利弗尼亚审判的囚徒遭几名白人典狱官的辱骂和体罚，日复一日负责把大石凿成碎石，直至1965年1月被调至石灰矿场干活。一开始，曼德拉被禁止戴墨镜，石灰折射的强光使他的视力永久性受损。他利用晚上的时间攻读LLB学位，但他不允许读报，曾几次因藏有偷带

进来的报纸而被单独监禁。曼德拉被定为最低级，即：丁等囚犯，因此每六个月才允许一次探视和一封书信来往，但所有书信都被严格审查。

为改善监狱条件，政治囚犯会发起罢工和绝食，并将之视为小型的反种族隔离斗争，但曼德拉认为绝食不怎么起作用。非国大的囚犯把曼德拉、西苏鲁、戈万·姆贝基（Govan Mbeki）和雷蒙德·莫翰拉巴（Raymond Mhlaba）选为四人核心领导小组；同时，曼德拉也加入了一个代表岛上所有政治囚犯的小组“乌伦迪”，并通过该小组与泛非大以及游击战协会的成员取得联系。曼德拉开创了“罗本岛大学”，囚犯们互相教授自己擅长的专业知识。他与同志们辩论同性恋和政治等话题，就政治上和姆贝基、哈里·瓜拉等马克思主义者进行了激烈的争论。曼德拉虽然每周日参加基督教的礼拜，但他也对伊斯兰教有所研究。他也学习阿非利加语，希望与狱官之间相互尊重，并改变他们的看法，使之支持曼德拉的事业。很多政治上的大人物探访曼德拉；其中意义最重大的是进步党的自由议会代表海伦·苏斯曼（Helen Suzman）的探访，她在监外积极支持曼德拉的事业。1970年9月，他与英国工党议员丹尼斯·希利（Dennis Healey）见面。南非司法部长吉米·库鲁格（Jimmy Kruger）于1974年12月前来探望，但他和曼德拉并不意气相投。曼德拉的母亲于1968年到狱中探视，不久后逝世；他的长子泽比次年死于车祸；曼德拉被禁止参加这两人的丧礼。他的妻子因政治运动经常被监禁，因此极少能探访，他的女儿于1975年12月首次探监；维尼于1977年获释，但被迫在布兰德堡居住，所以仍然无法到狱中探望。

1967年起，监狱条件得以改善——给黑人囚犯提供长裤，而不是以前的短裤；允许进行体育比赛；食物质量也提高了。曼德拉后来指出“尽管我们的处境窘迫，但足球让我们感到生机活力和成功感”。1969年，戈登·布鲁斯（Gordon Bruce）为曼德拉制定了越狱计划，但后来一位南非国家安全局的特务介入，想在曼德拉逃亡时把曼德拉击毙，于是越狱计划取消。1970年，皮尔特·巴登福克斯特（Piet Badenhorst）警官出任狱长。曼德拉眼看着对囚犯的身体和精神虐待越来越严重，他向来访的法官抱怨，于是法官把巴登福克斯特调岗了。新上任的威利·威廉姆斯（Willie Willemse）警官与曼德拉建立了合作的关系，并积极改善监狱状况。

1975年，曼德拉成为甲等囚犯，被准许更多的访客和书信来往；他与曼戈苏图·布特莱齐(Mangosuthu Buthelezi)和德斯蒙德·图图等反种族隔离积极分子有书信来往。这一年，他开始写自传，当时自传被偷运到伦敦，但一直未被出版；狱官发现了其中的几页，于是他的学习特权被中止了四年。这几年里，他把空余时间花于园艺和阅读，直至1980年，他又重新开始攻读LLB学位。

60年代末之前，曼德拉的声誉远不如斯蒂弗·比科（Steve Biko）和黑人觉醒运动（BCM）。BCM认为非国大的做法不起作用，于是发起激进的行动，但1976年索韦托起义后，很多BCM激进分子被监禁于罗本岛。虽然曼德拉不认同他们的激进主义，也瞧不起反种族隔离的白人激进分子，但他试着与这些年轻的激进分子建立关系。1978年7月，曼德拉庆祝60岁生日时，他的苦境又重新引起了国际上的关注。他获得莱索托政府颁发的荣誉博士学位，1979年印度政府颁发的“尼赫鲁国际理解奖”，以及1981年苏格兰颁发的“格拉斯哥城市自由奖”。1980年3月，记者珀西·戈博扎（Percy Qoboza）发起了“释放曼德拉！”的口号，触发了一场国际运动，最于使联合国安理会也呼吁释放曼德拉。在越来越多的外界压力下，南非政府还是拒绝释放曼德拉，仗着强大的冷战同盟国的支持——一是美国总统里根，二是英国首相撒切尔夫人；他们都认为曼德拉是共产主义恐怖分子，并支持打压非国大。