Родился 20 января 1958 г. в г. Улангом (центр Убсунурского аймака).
В 1976 г. окончил школу в г. Улангом.
В 1981 г. окончил физико-математический факультет Монгольского государственного университета (г. Улан-Батор) по специальности биофизика.
С 1981 по 1990 г. - преподаватель кафедры биофизики физико-математического факультета Монгольского государственного университета.
Во время демократической революции в 1990 г. был одним из ее участников и активистов, создавших Социал-демократическое движение.
С 1990 по 1992 г. - секретарь Монгольской социал-демократической партии.
С 1992 по 1994 г. - директор компании с ограниченной ответственностью "Этот день".
С 1994 по 1996 г. и с 1999 по 2000 г.- генеральный секретарь МСДП.
В 1996-2000 гг. и 2008-2012 гг. - член Великого государственного хурала (ВГХ, парламент Монголии).
С 1998 по 1999 г. – министр сельского хозяйства и промышленности.
В 1999-2000 гг. возглавлял постоянный комитет ВГХ по вопросам безопасности и внешней политики.
В 2000 г. вошел в руководство Демократической партии Монголии (ДПМ), образованной 6 декабря 2000 г. путем слияния ряда демократических партий Монголии, в числе которых была Монгольская социал-демократическая партии.
С 2000 г. по 2001 г.- секретарь парторганизации ДПМ в столичном районе Сонгинохайрхан, с 2001 г. по 2003 г. - генеральный секретарь ДПМ, с 30 августа 2008 г. - председатель ДПМ.
В 2004 г. - заместитель председателя Управления делами правительства Монголии.
В 2004-2006 гг. занимал должность министра финансов.
С 2006 г. по 2008 г. - представитель ДПМ в парламенте.
В 2008 г. - глава Совета политического планирования ДПМ.
С 20 сентября 2008 г. - первый заместитель премьер-министра Монголии.
В ходе парламентских выборов 28 июня 2012 г. Демократическая партия Монголии получила в ВГХ 31 мандат из 76. В соответствии с уставом партии, пост главы правительства на следующие четыре года должен занять ее председатель.
16 июля 2012 г. на заседании национального координационного комитета ДПМ кандидатура Н. Алтанхояга получила абсолютную поддержку.
9 августа 2012 г. ВГХ Монголии утвердил кандидатуру Н. Алтанхояга на пост 27-го премьер-министра страны. За него проголосовали около 72% парламентариев.
5 ноября 2014 г. ушел в отставку под давлением оппозиции из-за ухудшения экономической ситуации в стране. Алтанхояг подвергся критике депутатов из оппозиционной Монгольской народной партии и некоторых однопартийцев, которые обвинили его в коррупции и некомпетентности.
Награжден орденом Трудового Красного Знамени (Монголия, 2006).
Владеет английским и русским языками.
Любит путешествовать по стране, в том числе пешком и верхом на лошади. Увлекается фотографией, в Монголии периодически проходят выставки его фоторабот.