Największym poparciem cieszyli się pośród mniejszości etnicznych, w tym Gurkhów.
W 1998 roku w partii doszło do secesji skrzydła umiarkowanego – rozłamowcy powołali Patriotyczną Ligę Komunistów.
Według części źródeł maoiści współpracowali z naksalitami z Indii (konkretnie Komunistyczne Centrum Maoistowskie i Ludowa Grupa Wojenna) oraz separatystami z United Liberation Front of Assam. Rozpowszechnione było także przekonanie o wspieraniu KPN (Maoistowskiej) przez rząd ChRL, które było błędne.
Na początku XXI wieku rząd rozpoczął rozmowy z buntownikami. Do końca 2006 roku podpisano kilka umów kończących konflikt.
Legalna działalność Po zakończeniu kampanii rebelianckiej, maoistów dopuszczono do legalnej działalności. Wystartowali w wyborach parlamentarnych w 2008 roku, w których odnieśli zwycięstwo, zdobywając 38% głosów i 240 mandatów (na 601). Zwycięzcy wyborów zapowiedzieli, że nie chcą przekształcić Nepalu w państwo socjalistyczne oraz trwanie przy gospodarce rynkowej. KPN (m) utworzyła rząd koalicyjny z Kongresem Nepalskim i Komunistyczną Partią Nepalu (Zjednoczeniem Marksistowsko-Leninowskim). Premierem został Prachanda. 28 maja 2008 nowo wybrane Zgromadzenie Konstytucyjne ogłosiło Nepal republiką. Prachanda w 2009 roku podał się do dymisji.