在這裏，曼德拉還被允許會見那些還在監獄的同誌，商議如何進一步和政府談判。有一位名叫托克尤·塞克斯維爾的“民族之矛”的成員第一次同曼德拉見麵時，看到他生活在如此舒適的環境裏，竟誤以為曼德拉已經變節了。他回憶說：“我看到，納爾遜的房間裏有台電視機，這已經夠糟糕了，後來我又看到一台。兩台電視機！我覺得，這是確鑿的證據，他已經在敵人的糖衣炮彈前變節投敵了！”
曼德拉笑著向他解釋說：“另一台機器不是電視機，而是微波爐。”說著，他端來一杯水，把杯子放到微波爐裏，按下按鈕。過了一會兒，曼德拉從裏麵取出一杯熱氣騰騰的開水。
在此期間，曼德拉同尼爾·巴納德又進行了好幾輪談判。終於到1989年3月，尼爾·巴納德向博塔總統轉交了曼德拉的一封信。在信中，曼德拉指出，唯一能夠讓南非實現和平穩定的途徑，就是通過協商解決問題。他說：“南非屬於一切居住在南非的全體公民，沒有黑人和白人之分。黑人是非洲人，白人也是非洲人，南非不但需要多數民族的黑人，也需要少數民族的白人。”
1989年7月5日，博塔總統決定同曼德拉見麵，他們將這次見麵定義為“禮節性拜訪”。博塔是種族隔離政策的堅定倡導者，此人脾氣火爆，有“大鱷魚”之稱，南非黑人民眾將他視為白人種族統治的象征。
在與博塔總統會麵之前，曼德拉起草了一份政治聲明，闡述了自己的主張和非洲人國民大會對暴力的看法，這就是後來被稱為“5000字備忘錄”的文件。他在聲明中這樣說道：
現在事實已經非常明顯了，政府目前麵臨的問題，並不是非洲人國民大會拒絕放棄暴力鬥爭，而是政府還沒有準備好將權利還給黑人。它仍然執著於白人統治，所以，它隻能容忍那些在種族隔離製度下俯首稱臣的黑人，而不能容忍那些起來反抗的黑人。
這才是政府拒絕與我們對話的真正原因：它要求我們解除自己的武裝，但它卻可以繼續運用暴力來對付我們。
當天上午，南非監獄管理局局長親自來接曼德拉，驅車來到開普敦的總統官邸。促進這次會麵的情報局局長尼爾·巴納德和司法部部長科比·庫切正在總統辦公室外麵等候著。當曼德拉準備進入總統辦公室時，尼爾·巴納德忽然做了一個令所有人都感到意外的動作：他跪在曼德拉麵前，替他係好了鞋帶。
尼爾·巴納德敲了敲總統辦公室的門，然後推門而入。曼德拉回憶這一曆史性時刻時說：
博塔從他的豪華辦公室對麵朝我走來。顯然，他事先已經對自己的步幅作過演練，因為我們正好到達屋子中間的時候走到了一起。他向我伸出手，臉上笑容可掬，事實上，從這一刻起，我就完全放鬆了下來。他客氣、謙恭而友好，顯得有些令人難以置信。
在交談的過程中，曼德拉請求他釋放沃爾特·西蘇魯，原因是西蘇魯身體不佳，應該早日獲釋。博塔聽後，馬上對尼爾·巴納德說：“巴納德博士，你清楚這個問題。我以為你已經向曼德拉先生解釋過了。不過，我認為，我們一定得幫助他。我看這事必須解決，由你來處理。”尼爾·巴納德馬上說：“好的，總統先生。”
會談結束後，曼德拉和博塔兩人發布了一個聲明，聲明提出兩人“堅決支持南非的和平發展”。這句話背後的意思是，非洲人國民大會將有可能和政府通過會談達到和解，沃爾特·西蘇魯等7名政治犯也有可能被無罪釋放。
然而，讓曼德拉萬萬沒想到的是，就在他們會談後的一個月，博塔總統居然因病辭職了！