Lieutenant General Nadeem Taj was commissioned in the Pakistan Army's Punjab Regiment in 1972. He was promoted to Major General on 1 February 2002 and was already serving as the Military Secretary (MS) to the President of Pakistan (different from Military Secretary (MS), GHQ). It was during this time when Musharraf's convoy was attacked in Rawalpindi. Shortly after that incident, Taj was appointed Director General of Military Intelligence (DGMI) in December 2003 in place of the newly promoted-Lt. Gen. Tariq Majid who proceeded to be the new CGS. Taj was himself replaced as President's MS by Maj. Gen. Shafaatullah Shah. Taj continued as DGMI till February 2005, when he was replaced by Maj. Gen. Nadeem Ijaz.

He then moved on to become General Officer Commanding (GOC) 11th Infantry Division Lahore and continued till 24 April 2006, when he obtained the role of Commandant of the Pakistan Military Academy (PMA) at Kakul, Abbottabad District. It was from there that he was promoted to the position of ISI chief on 21 September 2007.