As a player, he captained the Indian national team that won a bronze medal at the 1970 Asian Games.
Nayeemuddin was first appointed coach of India in 1997. He won the South Asian Football Federation Cup by beating the Maldives 5–1 and reached the semi-finals of the Nehru Cup for the first time. His time in charge of the national team was blighted with no practice matches between September 1997 and November 1998 before the 1998 Asian Games. His role with India ended after the games in December 1998. His second role with India began when he succeeded Sukhwinder Singh as India coach in 2005 but left in 2006 after poor performances against Japan and Yemen when qualifying for the 2007 Asian Cup. He was appointed coach of Bangladesh in July 2007 but left the position in November of the same year. He is now the head coach of Brothers Union, Dhaka.