Sexwale nació en el township de Orlando West, en Soweto. Su padre era conserje en el Johannesburg General Hospital y había sido veterano de las fuerzas contra Alemania en la Segunda Guerra Mundial.^[1]​ Sexwale creció bajo la influencia de los disturbios de Soweto. En 1973 se graduó de la Escuela Secundaria Orlando West.

Para finales de 1960, Sexwale se hizo miembro del Movimiento de Conciencia Negra de Steve Biko y se convirtió en líder regional del movimiento estudiantil radical South African Students' Movement.^[2]​ A principios de 1970, se unió al brazo armado del Congreso Nacional Africano, Umkhonto we Sizwe ("lanza de la nación").^[3]​ Encontrándose en Suazilandia, finalizó un Certificado en Administración de Empresas en la University of Botswana, Lesotho and Swaziland.^[4]​ En 1975, Sexwale debió exiliarse, realizando estudios militares en la Unión Soviética, donde se especializó en ingeniería militar.^[5]​

Tras regresar a Sudáfrica en 1976, Sexwale, junto con otras 11 personas, fue capturado tras una escaramuza con las fuerzas de seguridad sudafricanas. Luego de casi dos años de juicio en la Corte Suprema de Justicia de Sudáfrica en Pretoria,^{[cita requerida]} fue procesado y condenado por cargos de terrorismo y conspiración para derrocar al gobierno. En 1977, Sexwale fue enviado a la prisión de máxima seguridad Robben Island para cumplir con una condena de 18 años.^[6]​ Mientras se encontraba preso en Robben Island, estudió Comercio en la Universidad de Sudáfrica.^[3]​ Sexwale fue liberado en junio de 1990 bajo los términos del Acuerdo Groote Schuur entre el gobierno del Partido Nacional y el Congreso Nacional Africano.^[3]​ Pasó en total 13 años en prisión.^[3]​

En aquellos años, su defensa legal fue asumida parcialmente por Judy van Vuuren. Comenzaron una relación personal cuando éste se encontraba en prisión, y se casaron poco después de su liberación en 1990.^[3]​

Luego de su liberación, Sexwale regresó a Johannesburgo, donde se desempeñó como líder del departamento de vinculación en la sede del Congreso Nacional Africano. Fue subsecuentemente nombrado como titular de los proyectos sociales, donde trabajba en la sede militar del CNA. En septiembre de 1990, fue electo como miembro del comité ejecutivo del CNA en la región de Pretoria-Witwatersrand-Vereeniging (PWV).

Luegos de las elecciones de abril de 1994, Sexwale fue electo como el primero en ocupar el cargo de Primier Ministro de la nueva provincia PWV (luego renombrada como provincia Gauteng en diciembre de 1994). En su gestión, fue alabado por llevar estabolidad a townships políticamente volátiles e inestables. Sexwale dejó la política para trabajar en el sector privado en 1998. Las razones del salto nunca quedaron del todo claras, pero se creyó que se sentía sofocado por las restricciones impuestas desde el gobierno central, como también el cansancio que generaban las intrigas del Congreso Nacional Africano.^{[cita requerida]} Otras especulaciones afirmaban que Sexwale abandonó la política debido a fuertes desacuerdos con el entonces vicepresidente de Sudáfrica, Thabo Mbeki.^{[cita requerida]} Otras especulaciones señalaban que su matrimonio le abrieron oportunidades en un ambiente financiero dominado por sectores blancos, las cuales no estaban fácilmente disponibles para líderes negros.^{[cita requerida]} Sexwale, Cyril Ramaphosa y Mbeki habían sido vistos como posibles candidatos presidenciales cuando Mandela decidió abandonar la política partidaria. Cuando Thabo Mbeki terminó posicionandose como el candidato preferido, tanto Sexwale como Ramaphosa abandonaron la política para desarrollar una carrera en el ámbito empresarial.^{[cita requerida]}

El 7 de enero de 2007, The Sunday Times informó que Sexwale comenzó su campaña para un cargo en el CNA, de manera de estar preparado para, llegado el momento, reemplazar a Thabo Mbeki como Presidente de Sudáfrica en 2009. Sexwale admitió en el programa BBC's Hard Talk que si las estructuras del partido le pidiesen competir para llegar a la presidencia del partido, lo consideraría seriamente.^[7]​ Fue elegido como uno de los 80 miembros del Comité Nacional Ejecutivo del partido en diciembre de 2007, resultando en el décimo lugar, con 2.198 votos.^[8]​

El 10 de mayo de 2009, el presidente Jacob Zuma designó a Sexwale como Ministro de Asentamientos Humanos,^[9]​ ministerio que reemplazó al Departamento de Vivienda.