在这里，曼德拉还被允许会见那些还在监狱的同志，商议如何进一步和政府谈判。有一位名叫托克尤·塞克斯维尔的“民族之矛”的成员第一次同曼德拉见面时，看到他生活在如此舒适的环境里，竟误以为曼德拉已经变节了。他回忆说：“我看到，纳尔逊的房间里有台电视机，这已经够糟糕了，后来我又看到一台。两台电视机！我觉得，这是确凿的证据，他已经在敌人的衣炮弹前变节投敌了！”

曼德拉笑着向他解释说：“另一台机器不是电视机，而是微波炉。”说着，他端来一杯水，把杯子放到微波炉里，按下按钮。过了一会儿，曼德拉从里面取出一杯热气腾腾的开水。

在此期间，曼德拉同尼尔·巴纳德又进行了好几轮谈判。终于到1989年3月，尼尔·巴纳德向博塔总统转交了曼德拉的一封信。在信中，曼德拉指出，唯一能够让南非实现和平稳定的途径，就是通过协商解决问题。他说：“南非属于一切居住在南非的全体公民，没有黑人和白人之分。黑人是非洲人，白人也是非洲人，南非不但需要多数民族的黑人，也需要少数民族的白人。”

1989年7月5日，博塔总统决定同曼德拉见面，他们将这次见面定义为“礼节性拜访”。博塔是种族隔离政策的坚定倡导者，此人脾气火爆，有“大鳄鱼”之称，南非黑人民众将他视为白人种族统治的象征。

在与博塔总统会面之前，曼德拉起草了一份政治声明，阐述了自己的主张和非洲人国民大会对暴力的看法，这就是后来被称为“5000字备忘录”的文件。他在声明中这样说道：

现在事实已经非常明显了，政府目前面临的问题，并不是非洲人国民大会拒绝放弃暴力斗争，而是政府还没有准备好将权利还给黑人。它仍然执着于白人统治，所以，它只能容忍那些在种族隔离制度下俯首称臣的黑人，而不能容忍那些起来反抗的黑人。

这才是政府拒绝与我们对话的真正原因：它要求我们解除自己的武装，但它却可以继续运用暴力来对付我们。

当天上午，南非监狱管理局局长亲自来接曼德拉，驱车来到开普敦的总统官邸。促进这次会面的情报局局长尼尔·巴纳德和司法部部长科比·库切正在总统办公室外面等候着。当曼德拉准备进入总统办公室时，尼尔·巴纳德忽然做了一个令所有人都感到意外的动作：他跪在曼德拉面前，替他系好了鞋带。

尼尔·巴纳德敲了敲总统办公室的门，然后推门而入。曼德拉回忆这一历史性时刻时说：

博塔从他的豪华办公室对面朝我走来。显然，他事先已经对自己的步幅作过演练，因为我们正好到达屋子中间的时候走到了一起。他向我伸出手，脸上笑容可掬，事实上，从这一刻起，我就完全放松了下来。他客气、谦恭而友好，显得有些令人难以置信。

在交谈的过程中，曼德拉请求他释放沃尔特·西苏鲁，原因是西苏鲁身体不佳，应该早日获释。博塔听后，马上对尼尔·巴纳德说：“巴纳德博士，你清楚这个问题。我以为你已经向曼德拉先生解释过了。不过，我认为，我们一定得帮助他。我看这事必须解决，由你来处理。”尼尔·巴纳德马上说：“好的，总统先生。”

会谈结束后，曼德拉和博塔两人发布了一个声明，声明提出两人“坚决支持南非的和平发展”。这句话背后的意思是，非洲人国民大会将有可能和政府通过会谈达到和解，沃尔特·西苏鲁等7名政治犯也有可能被无罪释放。

然而，让曼德拉万万没想到的是，就在他们会谈后的一个月，博塔总统居然因病辞职了！