W latach 2004–2006 pełnił funkcję ministra finansów w rządzie premiera Cachiagijna Elbegdordża.
W wyniku wyborów parlamentarnych z 29 czerwca 2008 powtórnie dostał się do parlamentu. Po rezygnacji z funkcji lidera Partii Demokratycznej przez Elbegdordża pod koniec sierpnia 2008 z powodu słabego wyniku wyborczego partii (26 mandatów), Altanchujag 2 września 2008 został wybrany jego następcą. Pod jego przywództwem Partia Demokratyczna postanowiła zawiązać wielką koalicję z Mongolską Partią Ludowo-Rewolucyjną (od 2010 występującą pod nazwą Mongolska Partia Ludowa). 19 września 2008 Norowyn Altanchujag objął stanowisko pierwszego wicepremiera w gabinecie premiera Sandżaagijna Bajara„Mongolian parliament appoints new gov’t”, People’s Daily Onilne, 20 września 2008..
28 października 2009, po przyjęciu dymisji premiera Bajara z powodów zdrowotnych, parlament mianował Altanchujaga pełniącym obowiązki premiera do czasu powołania nowego szefa rządu. Tego samego dnia Mongolska Partia Ludowo-Rewolucyjna na stanowisko premiera mianowała ministra spraw zagranicznych Süchbaataryna Batbolda. 29 października 2009 parlament zatwierdził Batbolda na stanowisku szefa rządu.