1985年底，67岁的曼德拉在沃尔克医院的体检中，被查出前列腺肥大。对于一个60多岁的老人来说，这是非常常见的疾病，但泌尿科医生威廉姆·劳布舍尔坚持要求动手术。
在手术的前一天，曼德拉的病床前来了一位特殊的探视者——南非司法部长科比·库切。曼德拉像主人欢迎老朋友一样问候科比·库切，让他大为惊讶。日后，科比·库切回忆说：“我第一眼看到他，马上意识到，这个人天生就是领袖。他谦虚绅士，彬彬有礼，医务人员都很喜欢他。他们当然知道这是个囚犯，却对他十分尊敬。他显然主宰着周围的一切。”
曼德拉出院后，并没有回到波尔斯穆尔监狱顶楼那的那间4人牢房，而是被单独关押在一个囚室。这并不是对他的惩罚，而是朝释放他迈出的第一步，目的是方便政府秘密保持与曼德拉接触。曼德拉的朋友阿米纳·卡查利亚来监狱探望他时，感到他的精神状态非常好：“我有一种感觉，改变就是从那个时候开始的。他必须要承担起责任，并尝试取得突破。他意识到有一天他将出狱，有机会亲自实现民主。这便是他行动起来的原因。”
曼德拉有了一个做伴的看守，叫克里斯托·布兰德。布兰德是一个单纯、善良的白人，从小就对曼德拉崇拜有加。两人在一起时间长了，布兰德更是把曼德拉当成父亲看待。布兰德的儿子出生后，他偷偷地将其带到监狱来，让曼德拉跟孩子玩耍。
1988年，世界范围内举行了很多活动，庆祝曼德拉的70岁生日。6月，英国广播电台策划了一场名为“70岁的自由”的演唱会，约7.2万人涌入伦敦的温布利体育场参加了这场盛会。观众和多位世界级的艺术家一起合唱《释放纳尔逊·曼德拉》的歌，其中有惠特尼·休斯顿和亨瑞·贝拉方特。卡特拉达在狱中给一位朋友写信说：“除了上帝的生日，没有谁的生日像纳尔逊的70大寿这般受到这么多人的庆祝，你难道不感到震撼吗？”
同年，博塔总统召见南非国家情报局局长尼尔·巴纳德，对他说：“巴纳德先生，我想要你现在去见曼德拉先生，看看我们能不能跟曼德拉和非洲人国民大会之间找到一条和解之路。搞清曼德拉对于共产主义持什么观点，然后设法获悉曼德拉和非洲人国民大会对和解是不是感兴趣。”
尼尔·巴纳德原来是奥兰治大学的一位政治学讲师，在学校时被誉为天才。后来，博塔总统招聘他为国家情报机构的最高负责人。此人身材高大粗壮，思维清晰，堪称南非政府“第一能吏”。
尼尔·巴纳德同曼德拉第一次见面的地点，是波尔斯穆尔监狱的监狱长办公室。当他第一次见到曼德拉时，几乎和科比·库切一样吃惊。他回忆说：“曼德拉先生进门后，我就马上感到，此人虽然身穿囚服，但他有一股不可侵犯的威严，人格魅力不容小觑。”
此次会面，两人并没有就和解做深入的探讨，因为尼尔·巴纳德觉得在这种场合下谈判，是对曼德拉的不尊重。他解释说：“让身穿着囚服的人来讨论国家的前途，这显然让人无法接受。我决定再安排一次会面，让曼德拉穿着符合其人格尊严的服装来。”
第二次见面，是在波尔斯穆尔监狱长威利·威廉斯的家中。那天，曼德拉穿着平整的西服，来到威利·威廉斯家出席晚餐。在这次会面中，两人在桌上谈了一个多小时。尼尔·巴纳德指责非洲人国民大会要为最近发生的暴力事件负责，并且必须放弃暴力斗争。
曼德拉反驳说，暴力事件应该由政府负责，因为政府堵死了和平请愿的道路，被压迫者们只能选择暴力斗争。非洲人国民大会一直主张用和平的方式解决问题，放弃暴力的主动权在政府一方。
此次会谈结束后，曼德拉并没有回到波尔斯穆尔监狱，而是被送往帕尔镇的维克托·弗斯特监狱。与以往不同的是，这回曼德拉没有住在囚室，而是被带到一所宽敞的房子里。这是一个很大的平房，墙面被粉刷得雪白，还有宽敞的花园和游泳池。曼德拉还拥有了一名私人厨师——杰克·斯瓦特。他的职责是为曼德拉做饭，并接访来宾，打扫卫生。
在这里，曼德拉还被允许会见那些还在监狱的同志，商议如何进一步和政府谈判。有一位名叫托克尤·塞克斯维尔的“民族之矛”的成员第一次同曼德拉见面时，看到他生活在如此舒适的环境里，竟误以为曼德拉已经变节了。他回忆说：“我看到，纳尔逊的房间里有台电视机，这已经够糟糕了，后来我又看到一台。两台电视机！我觉得，这是确凿的证据，他已经在敌人的糖衣炮弹前变节投敌了！”
曼德拉笑着向他解释说：“另一台机器不是电视机，而是微波炉。”说着，他端来一杯水，把杯子放到微波炉里，按下按钮。过了一会儿，曼德拉从里面取出一杯热气腾腾的开水。
在此期间，曼德拉同尼尔·巴纳德又进行了好几轮谈判。终于到1989年3月，尼尔·巴纳德向博塔总统转交了曼德拉的一封信。在信中，曼德拉指出，唯一能够让南非实现和平稳定的途径，就是通过协商解决问题。他说：“南非属于一切居住在南非的全体公民，没有黑人和白人之分。黑人是非洲人，白人也是非洲人，南非不但需要多数民族的黑人，也需要少数民族的白人。”
1989年7月5日，博塔总统决定同曼德拉见面，他们将这次见面定义为“礼节性拜访”。博塔是种族隔离政策的坚定倡导者，此人脾气火爆，有“大鳄鱼”之称，南非黑人民众将他视为白人种族统治的象征。
在与博塔总统会面之前，曼德拉起草了一份政治声明，阐述了自己的主张和非洲人国民大会对暴力的看法，这就是后来被称为“5000字备忘录”的文件。他在声明中这样说道：
现在事实已经非常明显了，政府目前面临的问题，并不是非洲人国民大会拒绝放弃暴力斗争，而是政府还没有准备好将权利还给黑人。它仍然执着于白人统治，所以，它只能容忍那些在种族隔离制度下俯首称臣的黑人，而不能容忍那些起来反抗的黑人。
这才是政府拒绝与我们对话的真正原因：它要求我们解除自己的武装，但它却可以继续运用暴力来对付我们。
当天上午，南非监狱管理局局长亲自来接曼德拉，驱车来到开普敦的总统官邸。促进这次会面的情报局局长尼尔·巴纳德和司法部部长科比·库切正在总统办公室外面等候着。当曼德拉准备进入总统办公室时，尼尔·巴纳德忽然做了一个令所有人都感到意外的动作：他跪在曼德拉面前，替他系好了鞋带。
尼尔·巴纳德敲了敲总统办公室的门，然后推门而入。曼德拉回忆这一历史性时刻时说：
博塔从他的豪华办公室对面朝我走来。显然，他事先已经对自己的步幅作过演练，因为我们正好到达屋子中间的时候走到了一起。他向我伸出手，脸上笑容可掬，事实上，从这一刻起，我就完全放松了下来。他客气、谦恭而友好，显得有些令人难以置信。
在交谈的过程中，曼德拉请求他释放沃尔特·西苏鲁，原因是西苏鲁身体不佳，应该早日获释。博塔听后，马上对尼尔·巴纳德说：“巴纳德博士，你清楚这个问题。我以为你已经向曼德拉先生解释过了。不过，我认为，我们一定得帮助他。我看这事必须解决，由你来处理。”尼尔·巴纳德马上说：“好的，总统先生。”
会谈结束后，曼德拉和博塔两人发布了一个声明，声明提出两人“坚决支持南非的和平发展”。这句话背后的意思是，非洲人国民大会将有可能和政府通过会谈达到和解，沃尔特·西苏鲁等7名政治犯也有可能被无罪释放。
然而，让曼德拉万万没想到的是，就在他们会谈后的一个月，博塔总统居然因病辞职了！
