Diplômé de l'école bantou d'Eshowe au Natal en 1972, il bénéficie d'une bourse scolaire pour suivre des études de droit à l'Université du Zululand et où il s'investit dans le syndicalisme étudiant.
Le , pour protester contre la répression du gouvernement durant les émeutes de Soweto, plusieurs bâtiments de l'université furent incendiés. Maduna fut alors accusé, arrêté et détenu de à juillet 1977.
Il est poursuivi pour terrorisme devant les tribunaux et acquitté.
Maduna est encore arrêté et poursuivi pour son appartenance à l'ANC, organisation interdite, et il est encore acquitté en 1979.
En 1980, Maduna quitte l'Afrique du Sud pour le Swaziland.
En 1983, il est arrêté et déporté hors du Swaziland. Il travaille alors à la base arrière de l'ANC au Mozambique, puis à celle de Tanzanie et enfin à Harare au Zimbabwe où il termine ses études.
Recruté au quartier général de l'ANC en Zambie, Maduna est un des fondateurs du comité constitutionnel de l'ANC et est à ce titre impliqué dans toute l'évolution du parti concernant les questions constitutionnelles et membre de toutes les délégations concernant la mise en place de négociations avec le gouvernement Afrikaner.
En 1991-1993, il est membre de la délégation de l'ANC aux négociations constitutionnelles avec le gouvernement de Frederik de Klerk qui ont lieu au Cap puis près de Johannesbourg.
Il est le coauteur avec Azhar Cachalia du chapitre sur les droits fondamentaux incorporés dans la nouvelle constitution provisoire de 1994.
Il en profite également pour terminer son cursus universitaire à l'Université du Witwatersrand.
Après les élections générales de 1994, Maduna devient vice-ministre des affaires intérieures du gouvernement de Nelson Mandela puis en juin 1996 ministre de l'énergie et des mines où il succède au flamboyant Roelof «Pik» Botha.
Après les élections de 1999, il est nommé ministre de la justice dans le gouvernement de Thabo Mbeki.
En 2004, il quitte le gouvernement et est recruté par le groupe sud-africain Sasol pour ouvrir le capital du groupe à une société à capitaux noirs. Par le biais du Maduna Group, il veut promouvoir l'investissement des capitaux noirs dans les entreprises en Afrique du Sud.
