W latach 2000–2004 zajmował stanowisko wiceministra spraw zagranicznych. Od 2004 do 2006 był ministrem handlu i przemysłu w gabinecie premiera Cachiagijna Elbegdordża. W latach 2004–2008 wchodził w skład parlamentu z ramienia Mongolskiej Partii Ludowo-Rewolucyjnej (obecna Mongolska Partia Ludowa). 19 września 2008 objął urząd ministra spraw zagranicznych i handlu w rządzie premiera Sandżaagijna Bajara. Jako szef dyplomacji, w lipcu 2009 gościł w kraju sekretarza generalnego ONZ Ban Ki-moona w czasie panelu dyskusyjnego w Ułan Bator poświęconego wprowadzeniem przez Mongolię Milenijnych Celów Rozwoju. W październiku 2009 reprezentował także premiera Bajara na spotkaniu Szanghajskiej Organizacji Współpracy.
28 października 2009, po rezygnacji z urzędu z powodów zdrowotnych przez premiera Bajara, Mongolska Partia Ludowo-Rewolucyjna nominowała Batbolda na stanowisko nowego szefa rządu. Do czasu zatwierdzenia nominacji przez parlament, p.o. premiera został wicepremier Norowyn Altanchujag. 29 października 2009 parlament zatwierdził Batbolda na stanowisku szefa rządu. Premier zobowiązał się do kontynuowania probiznesowej polityki poprzedniego gabinetu.