Comenzó su carrera política formando parte de la oposición anti-comunista y una vez instaurada la democracia multipardista en 1990 se unió al [[Partido Democrático (Mongolia)|Partido Democrático]]. Participó en varios gobiernos de su partido como ministro de Agricultura e IndustraIndustria, entre 1998 y 1999, y ministro de Finanzas entre 2004 y 2006. En 2008 pasó a liderar su partido y se convirtió en el viceprimer ministro en la gran coalición formada por los dos principales partidos y liderada por [[Sükhbaataryn Batbold]] del [[Partido del Pueblo de Mongolia]]. En las [[elecciones generales de Mongolia de 2012|elecciones]] de [[2012]] su partido fue el más votado y así en agosto Altankhuyag pudo recomponer la coalición pero ahora con él a la cabeza. Sin embargo la tensión entre los dos partidos seguía siendo muy alta, hasta el punto de que en diciembre el Partido del Pueblo abandonó la coalición, dejando a Altankhuyag en minoría.<ref>{{cita publicación |url=http://www.bbc.co.uk/news/world-asia-pacific-15460528 |título=Mongolia Profile: Leaders |autor= |editorial=BBC News |fecha=5 de diciembre de 2012 |fechaacceso=4 de enero de 2013 |idioma=inglés }}</ref>
