Nkunda werd in februari 1967 geboren in de Oost-Congolese provincie Noord-Kivu. Net als veel andere Congolese Tutsi’s begon hij zijn militaire carrière in het Rwandees Patriottisch Front (FPR), dat in 1994 de macht greep in buurland Rwanda tijdens de genocide op honderdduizenden Tutsi’s.Na twee jaar in het Rwandese leger sloot Nkunda zich aan bij rebellen in Zaïre, de huidige RDC. Onder leiding van Laurent-Désiré Kabila en met militaire steun van Rwanda en Angola verdreven die rebellen in 1997 de Zaïrese dictator Mobutu Sese Seko.

Kabila werd president en gaf de DRC haar huidige naam. In 1998 kwam het tot een breuk tussen Kabila en zijn voormalige bondgenoot Rwanda. Nkunda werd een van de commandanten van de opstandige Congolese Beweging voor Democratie (RCD) die in het oosten van Congo met Rwandese steun vocht tegen de regering in Kinshasa.

De oorlog, waarbij tal van buurlanden betrokken raakten, zou van 1998 tot 2003 aan meer dan 5 miljoen Congolezen het leven kosten. Na het vredesakkoord van 2003 ging de DRC deel uitmaken van de regering van nationale eenheid in Kinshasa; Nkunda werd gepromoveerd tot generaal.

Maar in juni 2004 stak de rebel in Nkunda alweer de kop op. Zijn mannen bezetten korte tijd Bukavu, de hoofdstad van de provincie Zuid-Kivu. Nkunda zei dat hij andere Tutsi’s moest beschermen. Die werden bedreigd door Rwandese Hutumilities die na de machtsgreep van de Tutsi’s in Rwanda de grens waren overgestoken. In 2005 vaardigde Congo een arrestatiebevel wegens oorlogsmisdaden uit tegen Nkunda, die inmiddels uit het regeringsleger was gezet.

De gevechten in het oosten van Congo bleven de volgende jaren voortduren. In januari sloot Nkunda vrede, maar in augustus brak het geweld weer los. „Ik heb er niet voor gekozen oorlog te voeren. Eigenlijk wilde ik verpleger worden, maar ik moest antwoorden op het hulpgeroep van de bedreigde bevolking”, aldus Nkunda.