新政府成立后，和解与团结依然是我要解决的首要问题，一个不团结的政府，只会在争执中分崩离析。
——1994年曼德拉答记者问
根据南非宪法，身为总统的曼德拉拥有不小的权力，他既是国家元首，也是政府的最高行政长官，就连副总统的职位也来自他的授权。曼德拉是一个天生的领袖，却并非一个天生的政治家，他总是会忘记自己总统的身份，忘记自己身后的内阁，在媒体面前滔滔不绝地谈论自己的个人想法。由于他远离社会太久，所以他常常会说出一些让听众觉得是天方夜谭的设想。这引来一些评论家的批判，他们认为曼德拉总是信口开河，并且具有独裁的倾向。
曼德拉的好友也时刻关注着曼德拉的言行，害怕他在权力之巅迷失自己，变成津巴布韦的穆加贝一样的酋长型独裁者。但很快他们就发现这样的担心是多余的，西苏鲁说：“我一点都不担心曼德拉会变成独裁者，他对非洲民主怀有无限敬意。”
在最初组建政府时，曼德拉希望尽可能建立起最广泛的联盟，把所有党派人士都吸收进来，但由于政策上的分歧，一些党派拒绝了他的邀请。根据之前的协议，新政府中必须为南非国民党保留几个席位，但具体把哪几个部门交给国民党，曼德拉和德克勒克分歧较大。德克勒克希望国民党至少拿到警察或国防部门中的一个，曼德拉则坚持所有武装都必须在非国大的控制之下。在这点上曼德拉表现出一个政治家应有的强硬，他不希望将有可能毁灭和平的武器交到曾经的对手手里。最后，德克勒克让步了，南非国民党最后得到了农业部、环境部以及矿业和能源部等几个没有多少实权的部长职位。
而最重要的几个部门都由曼德拉各个时期的老友把持着：国防部长乔·莫迪萨是曼德拉年轻时在约翰内斯堡的同事，外交部部长阿尔弗莱德·恩佐是1958年巴士抗议活动的领导人之一，交通运输部长是那个在罗本岛上经常向曼德拉提议越狱的麦克·马哈拉吉，住房部长也是曼德拉在罗本岛上的战友乔·斯洛沃。除此之外，还有一些青年才俊也被吸收到政府中来。
这届政府的最大特色就是多样性，这些部长来自不同的民族，具有不同的信仰。历经多年，他们终于从盟友、敌人变为了同事。有的人甚至在政府已经运转一年之后还说：“有时，我依然要掐一下自己才能确定这是什么地方。”当然，这届政府内阁的内部矛盾并不算突出，他们大多的争论是超越党派的。很多白人领导也在这个黑人占多数的政府里用心工作，甚至有时他们看起来才是“真正的民主革命者”。这也得益于非国大成员做出的表率作用，他们并未在每次政府会议前统一思想，而是在会议上进行合理的辩论，甚至有时候需要德克勒克去调停他们之间的争论。曼德拉对此感到欣慰，但这样的民主与和谐能否制定出最佳的政策，能否为人民的生活质量做出贡献，还需要时间的验证。
这届政府中，曼德拉对第一副总统姆贝基的依赖最严重。姆贝基的任务十分艰巨，曼德拉作为政府首脑，更多的作用体现在精神层面，而具体的琐碎事务都是由姆贝基操作的。而且，在曼德拉的盛名之下，姆贝基做好了得不到公众的褒奖，做错了却要站出来背黑锅，这也给他带来了相当大的压力。曼德拉一直在前面冲锋陷阵，姆贝基则在后方保证一切平稳运转。从这点来说，曼德拉的耀眼光环里有姆贝基的一份热度。
曼德拉一般两周主持一次内阁会议，并且就像他所喜爱的部落首领会议上的摄政王一样，他并不参与争论，而是在耐心听完所有发言后，作出一点总结和评判。但这不表示他对内阁的控制力有所减弱，由于他的年龄比其他人至少大20岁，加上一身的光环与荣耀，所以他们对曼德拉敬爱有加。
当然，曼德拉也并非不参与具体的事务，他对国家安全和情报这两块十分热心，每次内部会议他都会参加，并且认真地跟进细节，并适时做出指示。这时，他就像一个老地下工作者，认真、果断，一改往日的和气。因为他知道，这两项事关一个国家的生死。
一派和气之下，曼德拉和德克勒克以及布特莱奇的矛盾渐渐凸显出来。因为在和谈过程中，德克勒克曾纵容南非白人阵线和英卡塔对非国大的袭击，所以曼德拉并不信任他，尤其当曼德拉知道德克勒克曾在大选开始前对曾犯下罪行的警察进行补偿，更是怒不可遏。同时，德克勒克也对曼德拉的执政能力表示怀疑，最后，南非国民党退出了联合政府，德克勒克也辞去了副总统的职位。
另一方面，担任内政部长的布特莱奇依然抗拒非国大的领导，还在背后进行一些破坏行动：抵制制宪会议，号召祖鲁群众抵制政府，等等。曼德拉对布特莱奇实在忍无可忍，并表现出了少见的暴怒，他扬言不再向祖鲁地区进行经济支援。在德克勒克的斡旋下，他们再次进行和谈，但个人矛盾从未解决。幸运的是，曼德拉的一个得力助手帮他解决了祖鲁人的问题，那就是雅各布·祖马。曼德拉任命雅各布·祖马为新设立的夸祖鲁—纳塔尔省省长，祖马的朴实作风和谦和态度赢得了当地祖鲁人的信任，最终，在他的经营和斡旋下，英卡塔和非国大走向了和解，并维持了稳定的合作关系。布特莱奇知道大势已去，便也不再把对抗政府作为拉拢人心的手段。
曼德拉上任后的南非政坛处在过渡时期，南非各党派虽然有不少摩擦，但总体上都致力于消除党派纷争，实现跨种族发展，各大阵营相互交融渗透。国民党人和有色人、印度人的关系很好，纳塔尔省有不少白人支持英卡塔，相比之下一直致力于多种族团结的非国大反而获得了较少的支持，这是每个刚上任的执政党都要面临的问题。过了几年，这种融合的速度减慢了，黑人和白人在政坛的分野依然不小。曼德拉能赢得南非白人的尊敬，却很难争取到他们在政治上的支持，毕竟，团体利益才是政治的出发点和落脚点，在南非的经济实现真正的飞跃发展之前，白人只能作为既得利益者继续顽抗下去。