Kiedy 17 stycznia 1961 Patrice Lumumba został stracony w zbuntowanej Katandze najprawdopodobniej z inspiracji Moïse Tshombe lub Mobutu Sese Seko, Mulele początkowo objął funkcję ambasadora Konga-Leopoldville w Egipcie i Chińskiej Republice Ludowej w nowym rządzie Antoine'a Gizengi. W 1961 udał się na emigrację.
W 1963 powrócił do kraju, by w lipcu tegoż roku przygotować komunistyczne powstanie, rozpoczynając od części prowincji Kwilu, w której był szeroko znany. Przewodził wówczas ugrupowaniu Parti Solidaire Africain (PSA), która uznawała naczelne przywództwo uwięzionego wówczas Antoine'a Gizengi. Na czele drugiego ugrupowania stał Cleophas Kamitatoe. Oba odłamy partyjne zwalczały się z powodu różnic w poglądach ideologicznych i antagonizmów plemiennych. Mulele prowadził m.in. ćwiczenia młodzieży powstańczej w zasadach i technikach walki partyzanckiej, opierając się na tych wioskach, w których mógł zagwarantować sobie solidne poparcie, takich jak okolice zamieszkane przez Bapende. Poparcie dla powstania Mulele zawdzięczał powszechnemu poczuciu niesprawiedliwości represyjnego systemu i niezadowolenia z sytuacji ekonomicznej w kraju, w tym braku zarobków. Działania partyzanckie powstania Mulele miały na celu było zahamowanie jakichkolwiek wpływów w kraju rządu Cyrille'a Adouli.