Nassaji Mazandaran Company established the club in 1959. Nassaji entered the Qods cup in 1988 and soon after they entered the top division Azadegan League in 1991 and stayed there until 1995. They stayed in 2nd division until 2001 and when Iranian Football Federation decided to start a professional league, the Azadegan league became the second highest league in Iran. 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.