In February 1966, Nathan was transferred to the Ministry of Foreign Affairs. He served as Assistant Secretary and rose to be Deputy Secretary before being appointed Deputy Secretary of the Ministry of Home Affairs in January 1971. On 6 August of the same year, Nathan moved to the Ministry of Defence where he was Director of the Security and Intelligence Division (SID). In the Laju incident on 31 January 1974, members of the terrorist Japanese Red Army and the Popular Front for the Liberation of Palestine bombed petroleum tanks on Pulau Bukom off the coast of Singapore; Nathan was among a group of government officers who volunteered to be held hostage by the JRA and flown to Kuwait to secure the release of civilian hostages and ensure the terrorists' safe passage. For his bravery, in August 1974 he was awarded the "Pingat Jasa Gemilang" (Meritorious Service Medal).