1990年2月10日，德克勒克再次邀请曼德拉到自己的办公室，并直截了当地告诉曼德拉，他打算在第二天释放他。他说：“政府首先会用飞机将你送到约翰内斯堡，并在约翰内斯堡释放你。”
听到这个消息后，曼德拉并未表现出异常的高兴，反而要求在狱中再待一个星期，这样非洲人国民大会就可以安排好迎接仪式了。德克勒克表示反对，他担心非洲人国民大会组织大规模游行，使整个国家陷入混乱。1979年2月，长期流放的阿亚图拉·霍梅尼返回伊朗时，他大声疾呼：“我要重拳砸向政府的嘴巴。”结果在狂热民众的围攻下，不到10天，政府就垮台了。
曼德拉还坚持自己必须在温妮的陪伴下步行走出监狱的大门，然后向开普敦的人们发表讲话。德克勒克听完后皱着眉头想了想，决定和内阁成员们商量一下。
过了一会儿，德克勒克回来了，他告诉曼德拉：“现在延迟已经为时过晚了，因为政府已经将消息告诉国外的媒体了；不过我可以答应你，在监狱大门处释放你。”曼德拉只好答应了。
当天晚上，非洲人国民大会的成员们来到监狱，帮助曼德拉修改演讲稿。开普敦的律师杜拉赫·奥马尔和曼德拉待了两个小时，他发现曼德拉“显得很忧郁，沉浸在自己的思绪中。他可能知道将要发生什么。”
第二天，曼德拉跟往常一样凌晨4：30就起床了。吃完早餐并进行了一项体检之后，曼德拉再次和非洲人国民大会的成员们聚在一次，对演讲稿做最后的修改。他还将自己在波尔斯穆尔监狱里看过的书和报纸打包好，装了十几箱子，并和狱警们一一握手告别。
2月11日下午3点，曼德拉和妻子温妮手挽手走出了监狱的大门。无数的民众和记者将监狱门口围得水泄不通。曼德拉举起右拳，向欢迎他的人群致意。他说：“我终于走出监狱的大门了，这给了我巨大的喜悦和力量，虽然我现在已经71岁了，但却感觉人生才刚刚开始。”
从波尔斯穆尔监狱到市政大厦，开车45分钟就到了。司机没有应对重大集会的经验，居然没头没脑地朝着人群开去。等待已久的黑人们见到心中的领袖，马上将汽车团团围住。有的人不停地敲打着车窗，有的人爬上了车顶，摇动着车辆。曼德拉和温妮坐在车里，感觉自己像茫茫大海中的一叶扁舟。
直到晚上8点钟，曼德拉才来到了市政大厦。他站在市政大厦的顶层，握拳向底下的人高呼：“政权！再回来！非洲！再回来！”
随后，曼德拉向底下狂热的民众宣读了他的“出狱演说”：
朋友们，同志们，南非同胞们：
我以和平、民主和自由的名义，向你们大家致敬。今天，我不是作为一个先知站在你们面前，而是作为你们的公仆站在你们面前。你们经过不懈的奋斗和英勇牺牲，才使我有可能在今天站在这里，因此，我要把余生交到你们的手中。
在我获释的今天，我要向我的同胞以及全国各地每一个为我的获释作出过不懈斗争的同胞，致以亲切的和最热烈的感谢。
今天，大多数南非人，无论黑人还是白人，都已认识到种族隔离制度绝无前途。为了确保持久的和平与稳定，我们必须通过大规模的行动，来结束这种制度。只有各个组织和团体发动大规模的反抗行动，才能导致民主制度的建立。
种族隔离制度给这片古老的大陆带来了难以估量的灾难。无数个家庭的生活基础遭到了破坏，数百万人无家可归，还失去了工作。我们的经济到了崩溃的边缘，人民也陷入了政治斗争的汪洋大海之中。
我们之所以在1960年建立“民族之矛”并采取武装斗争，这纯属为反抗民族隔离制度的暴力而采取的自卫行动。
今天，我必须再次声明，需要武装斗争的因素依然存在。我们没有其他的选择，只有继续进行武装斗争。我们希望未来将会建立一个有利于和谈的环境，以便不再有必要开展武装斗争。
我是非洲人国民大会中忠诚而守纪律的一员，因此，我完全赞成非洲人国民大会所提出的战略战术。现在，我们需要把全国人民团结起来，这是一项非常艰巨的任务。任何一个领导者，都无法独自承担起这项重任。
作为领袖，我们的任务是向我们的组织阐明观点，并让民主制度去决定我们未来所走的道路。关于推行民主的问题，我必须强调一点：运动的领导人必须要从全国代表大会的民主选举中产生。这是一个必须坚持、永不妥协的原则。今天，我希望能向你们汇报：我和政府进行的一系列会谈，其目的都是为了让我们国家的政治局势正常化。
我希望强调一下，除了坚持要求在非洲人国民大会和政府之间进行会晤以外，我本人从未就我国的未来问题同政府进行过谈判。也就是说，真正的谈判还没有开始，因为谈判不能在人民背后进行。要通过谈判消灭种族隔离制度，就必须正视我国人民的压倒一切的要求，即建立一个民主的、不分肤色的和统一的南非。白人把持政权的状况必须结束。
我们应当从政治和经济制度上进行改革，以达到结束不平等的种族隔离的目的，并保证我们的国家彻底实现民主化。
我们的斗争已经到了最后的关头。我呼吁人民抓住这个机会，从而迅速地、不间断地推动民主化的进程。我们等自由等得太久了，我们不能再这样等下去了，现在就让我们在各条战线上加强斗争吧！如果现在放松努力，将会酿成大错，我们的后代都不会原谅这个错误。当地平线上浮现出自由的奇观时，我们应该尽最大的努力，紧紧地抓住它。只有通过纪律严明的群众运动，我们的胜利才有保障。
我呼吁白人同胞能够加入我们的行列，一起建立起一个新南非。自由运动也是你们的政治归宿。我们呼吁国际社会继续采取行动，来孤立这个实行种族隔离制度的政府。如果在目前取消对这个政府的制裁，彻底消灭种族隔离制度的进程就会有夭折的危险。
我们迈向自由的脚步是不可逆转的。我们不能让恐惧挡住了我们的道路。由统一的、民主的和不分肤色的南非实行****，是通向和平与种族和谐的唯一大道。
最后，我想回顾一下我在1964年受审时说过的话。这些话在当时和现在都一样千真万确。我说过：“我把我的一生都献给了黑人民众的解放事业。我反对白人统治，也反对黑人统治。我珍视民主和自由社会的理想，在那样的社会里，所有的人都和睦共处，拥有相同的机会。这是我的理想，我要努力去实现它。同时，如果有必要，我时刻愿意为我的理想付出生命。”
演讲结束后，曼德拉乘坐汽车离开市政大厦，去拜访图图大主教。通过图图大主教家的电话，美国总统乔治·布什、莱索托国王莫舒舒二世、赞比亚总统卡翁达向曼德拉获得自由表示了祝贺。
