Działalność polityczna Bhattarai rozpoczął działalność polityczną w czasie studiów w Indiach. W 1977 założył tam Stowarzyszenie Nepalskich Studentów. Następnie został jednym z głównych działaczy Komunistycznej Partii Nepalu (Masal). W 1991, po rozpadzie tej partii, przyłączył się do Komunistycznej Partii Nepalu (Centrum Jedności) (Communist Party of Nepal (Unity Centre)). W tym samym roku partia utworzyła swoją platformę wyborczą, Zjednoczony Front Ludowy Nepalu (Samyukta Janamorcha Nepal – United People's Front Nepal), z Bhattaraiem jako swoim liderem.
W 1994 Komunistyczna Partia Nepalu (Jedność Centrum) rozpadła się na dwie grupy. Bhattarai przyłączył się do grupy o bardziej radykalnych poglądach, która później przekształciła się w Komunistyczną Partię Nepalu (Maoistowską). Bhattarai zyskał popularność w czasie wojny domowej w Nepalu (1996-2006), wyrażając publicznie niezadowolenie z polityki króla. W owym czasie był jednym z nieoficjalnych rzeczników ugrupowania, jego twarz pojawiała się najczęściej w doniesieniach prasowych na temat walk.
Na początku 2005 wszedł w konflikt z liderem partii, Prachandą. Oskarżył go o tworzenie wokół siebie kultu jednostki. Konsekwencją tych oskarżeń stała się degradacja w strukturach partyjnych.