[2] Gbenye joined Patrice Lumumba's independence oriented Mouvement National Congolais (MNC-L) in the late 1950s, and became a prominent leader of the party by 1959.

Lumumba's eventual arrest and execution in January 1961 deeply angered Gbenye, though he did briefly return to his position as interior minister under Cyrille Adoula's coalition government.

He replaced Lumumba as president of the MNC-L.[2] However, Gbenye was seen as a political liability by the United States Central Intelligence Agency, which was largely responsible for Adoula's rise to power.

On 3 October, Gbenye, Bocheley Davidson, Gaston Soumialot, and other dissidents established the revolutionary organization Comité National de Libération.

[5] In 1964, under the leadership of Gbenye, Mulele and Soumialot, much of the eastern Congo was overrun by young rebel fighters who called themselves simba (lions).