Nkunda deltog från 1993 på tutsimilisen FPR:s sida i inbördeskriget i Rwanda. Vid FPR:s maktövertagande efter hutuextremisternas folkmord på tutsier 1994, återvände Nkunda till hemlandet, dåvarande Zaire, där han anslöt sig till den revolt som ledde till president Mobutus fall 1997. I det kongolesiska inbördeskriget 1998–2003 var Nkunda officer i den