Mandela heiratete seine erste Frau Evelyn Mase, die in Johannesburg lebte und ihre Ausbildung als Krankenschwester machte, im Jahre 1944. Evelyn war ein sehr zurückhaltendes und gut erzogenes Mädchen aus der Provinz. Mandela aber war schon damals sehr im politischen Geschehen des Landes involviert, wodurch ihm wenig Zeit für Familie und Ehe blieb. Die Ehe scheiterte und er ließ sich 1957 scheiden. Währenddessen kam eine junge Frau namens Nomzamo Madikizdar nach Johannesburg. Sie wurde die erste schwarze medizinische Sozialarbeiterin im Baragwanath Krankenhaus. Schon als Studentin kam sie in Kontakt mit ANC Mitgliedern. 1957 traf sie Mandela und war beeindruckt von ihm. Sie erkannte bald die Notwendigkeit der "ANC Womans League" und "Federation of South Africas Woman". Während Mandelas Prozess wegen Hochverrat trafen sich beide mehrfach. Ihre Zusammenkünfte führten im Juni 1958 zur Eheschließung. Diese Ehe stellte keines Weges eine Behinderung Mandelas in der Freiheitsbewegung dar. Es gab ihm sogar den nötigen Schwung. Im gleichen Jahr als Winnie (Nomzamo Madikizdar) Mandela mit ihrem ersten Kind schwanger war, wurde sie während einer Demonstration gegen das "Passgesetz" verhaftet und verlor ihre Arbeitsstelle.