In 2004 Nassaji was relegated to 2nd Division but they were promoted back to the Azadegan League at the end of the 2005–06 season.

On 3 August 2006 Nasser Hejazi signed as head-coach of Nassaji on a one-year deal for the 2006–07 season.

On 18 September 2023 in their debut 2023–24 AFC Champions League group stage fixtures, Nassaji won 2–0 against Mumbai City of India with goals coming from Ehsan Hosseini and Mohammad Reza Azadi.

Since the club was created, Nassaji has trained and played its home games at Vatani Stadium, which was built in the 1940s.

Note: Flags indicate national team as defined under FIFA eligibility rules; some limited exceptions apply.