W styczniu 1991 utworzył Komunistyczną Partię Nepalu (Zjednoczenie Marksistowsko-Leninowskie), powstałą ze zjednoczenia Komunistycznej Partii Nepalu (Marksistowskiej) i Komunistycznej Partii Nepalu (Marksistowsko-Leninowskiej). W 1993 objął funkcję sekretarza generalnego KPN (ZM-L). Od listopada 1994 do kwietnia 1995 pełnił funkcję wicepremiera oraz ministra spraw zagranicznych i obrony w rządzie premiera Man Mohana Adhikariego.
W kwietniu 2001 Madhav Kumar Nepal przewodził demonstracjom przeciwko rządowi premiera Girija Prasad Koirali, którego opozycja oskarżała o korupcję. Za udział w protestach został aresztowany"Nepal opposition members arrested", BBC News, 17 kwietnia 2001..
Po zdymisjonowaniu rządu, rozwiązaniu parlamentu i samowolnym przejęciu całej władzy w kraju przez króla Gyanendrę w październiku 2002, Madhav Kumar Nepal i jego KPN (ZM-L) przyłączyła się do protestów przeciw autorytarnym rządom i polityce króla"Nepal king faces opposition campaign", BBC News, 22 stycznia 2003..