同伊芙琳离婚后，很多朋友都在猜测曼德拉会不会再婚，因为他们看到曼德拉最近常常和一些女性在一起，比如莉莲·尼戈伊和鲁思·梦帕提。莉莲·尼戈伊是曼德拉的女性朋友之一，也是非洲人国民大会妇女联盟的领袖，她足智多谋，而且浑身散发着成熟的魅力。曼德拉的好朋友海伦·约瑟夫说：“你们两个人就是天作之合。”鲁思·梦帕提则是曼德拉律师事务所的秘书，她聪明伶俐，也很讨人喜欢。
没想到，俘虏了曼德拉的人，并不是莉莲·尼戈伊，也不是鲁思·梦帕提，更不是别的经验丰富的政坛人物，而是一个名不见经传的小姑娘——温妮·诺姆扎蒙·马蒂克泽拉。
温妮出生于蓬兰多的比扎那，那里几乎是南非最贫穷落后的地方，她的父亲祖父马兹恩吉酋长是一个富商，有29位妻子，后来皈依了卫理公会。温妮的父亲名叫哥伦布·玛迪基泽拉，他放弃了继承酋长的机会而成为了一名公职教师。温妮是他11个孩子中的第6个。
从小，温妮就和父亲比较疏远，倒是和祖母很亲近。温妮的好朋友法蒂玛·米尔说：“温妮独断专行的风格是从她的祖母那里继承来的，而她对漂亮服装的喜爱以及爱干净的习惯则比较像她的母亲。”
童年时期的温妮非常离经叛道，甚至有些暴力倾向。有一次，她用一块马口铁和一枚钉子做了一个掸子，并用这个掸子打破了她妹妹的嘴巴。为此，她遭到了母亲的鞭打，这让她铭记一生。温妮回忆说：“这就是生存，我从来都没有自己的衣服，所以我必须和兄弟姐妹们争抢，我们之间打架是寻常的事情。等慢慢长大了，我才开始感觉到羞愧。”
温妮的母亲格尔特鲁德据说有白人血统，她对宗教有着狂热的信仰。格尔特鲁德曾经在玛丽安希尔罗马天主教会受过教育，后来，她也成了当地的一名教师。作为一名虔诚的基督徒，她总是严格按照卫理公会教徒的方式来培养孩子们。
温妮回忆说：“当我还只有8岁的时候，母亲就常常把我和妹妹锁在房间里，强迫我们大声祈祷。当父亲在家的时候，母亲就把我们拉到花园里，在那里进行祈祷。每天3次，从不间断。小时候的我对这种宗教仪式一窍不通，但迫于母亲的威力，我只好照着她的样子去做。这一切给我留下了非常深的印象，到后来，我在中学里对教会表示反抗，因为我觉得，那也是对她这种家庭专制的反抗。”
相比较母亲来说，父亲在温妮心中的形象一直是温和而神圣的。父亲是一名历史教师，对他来说，科萨人的9次抗英战争永远是他课程的主题。每当碰到一些重大的节日，他都要把村里的孩子叫到一起，用慷慨激昂的语调去重复祖先当年的骄傲。
温妮至今还记得当年父亲讲课的情形：
当父亲开始教我历史时，我已经懂事了。比如，我还清清楚楚地记得他当年是怎样给我讲科萨人和英军之间的战争的。我们有教科书，但那是白人编写的。对于为什么会发生那9次战争，白人有他们自己的解释。父亲会把课本放到一旁，说：“好，这是书上说的。但实际情况是，这些白人侵占了我们的国家，要把我们赶出这片土地。黑人和白人之间的战争是由偷牛引起的。白人偷了我们的牛，我们要抢回来！”父亲就是这样教我历史的。
7岁的一天，温妮的姐姐维叶娃从寄宿学校回来，咳嗽不止。当天晚上，母亲便带她去附近的教堂祈祷，回来后，维叶娃开始咳血。没多久，维叶娃就在母亲的怀里死去了。温妮和她的兄弟姐妹们为死去的姐姐哭得死去活来。
可能是受维叶娃的传染，母亲不久后便染上了肺病，而且越来越严重。两年后，她也逝世了，年仅40岁。
母亲的葬礼是由当地的卫理公会办的，非常隆重，为此，父亲还专门宰了两头公牛和几只羊。
母亲死后，家里的生活更加艰难了。当时，温妮有一个最小的弟弟，只有3个月大。幼小的温妮便承担起了照顾弟弟的责任。“我9岁的时候，就要手忙脚乱地为弟弟准备喝奶的瓶子。晚上还要抱着他几个小时，喂他糖水，哄他睡觉。”同时，她还要干一些其他的农活。“我挤牛奶，照顾家里的绵羊和山羊，收割庄稼，这就是我肌肉发达的原因。”
第一次经历种族歧视，是在她十多岁的时候。一次，她和父亲到一家白人开的饭店里用餐。正在他们点好餐等着的时候，门口又进来了一家三口非洲人。他们风尘仆仆，嘴唇干裂，看起来走了很远的路。那个男的买了一块面包、一点糖和一瓶饮料，女的则抱着孩子坐在角落里等着。可能是由于太饿的关系，那个孩子忽然哇哇大哭起来。于是，女的解开衣服开始给孩子喂奶，而男的则掰下一块面包，想塞进孩子的嘴里。远处的白人服务员看到了这一幕，忽然大叫着跑过来，一边踢他们一边骂：“快起来，赶紧给我滚出去！”
温妮在一旁吓傻了，她实在不明白，那位白人服务员为什么要那么恶狠狠地对待他们一家三口。她问父亲，父亲只是淡淡地说：“这很正常，孩子，你要习惯这些。”
早在上初中的时候，曼德拉就成为了温妮和她的同学们的偶像。她们当中没有人见过曼德拉，但都对他极其崇拜。有些学生甚至以罢课的形式来表现自己对曼德拉的仰慕之情。
在中学学习的时间里，温妮渐渐开始展露出她的组织才能。一位中学同学回忆道：“她被选为各年级学生的总级长，负责监督从一年级到五年级的全体女生。当时的她性格内向，不喜欢多说话，但她的领导才能已经初露端倪了。我们共同成立了一个辩论俱乐部。她的神奇之处，在于她有办法迅速让同学们遵守纪律，并拧成一股绳。她的学习非常优秀，体育也很棒，常常在乌姆塔塔体育节上获奖。”
1953年，温妮来到约翰内斯堡参与社会工作。她住在叶普街的一家招待所，在简·霍夫迈尔社工学校学习。两年后，天资聪颖的她已经成了巴拉瓦纳斯医院的第一名黑人社工。
当时，与温妮一起住的还有一个名叫艾德莱迪·图库杜女孩，他是奥立弗·坦博的未婚妻，当时任总医院的护士长。有一天，曼德拉的族侄凯泽·马坦齐马来约翰内斯堡办事，正好碰见温妮。一见面，马坦齐马就喜欢上了她。
事后，马坦齐马对艾德莱迪说明了自己的心愿。艾德莱迪敷衍说：“那我得和温妮谈谈。”说实话，她并不喜欢这个年轻人。当艾德莱迪把这一情况告诉温妮后，温妮什么话都没说，既没表示接受也没表示拒绝。
很快，马坦齐马就回特兰斯凯去了。但是在那里，他几乎每天都要给温妮写情书。与此同时，温妮还听说马坦齐马已经派自己的手下去了蓬兰多，准备跟自己的父亲求婚。这种唐突的举动显然惹怒了温妮，从此之后，她就再也没有给马坦齐马回过信。
就在这个时候，曼德拉出现了。