Founded in 1962, the club was in Liga Artzit, then the second tier, in 1980-81. In 1983-84 they finished second from bottom, and were relegated to Liga Alef.
In 1998-99 they finished as runners-up in Liga Alef North, and were promoted back to Liga Artzit, which was now the third tier following the formation of the Israeli Premier League in 1999. After narrowly avoiding relegation in 2000-01 when they finished one place above the relegation zone, the club finished as runners-up the following season, and were promoted back to the second tier. In 2003-04 they finished as runners-(on goal difference), and were promoted to the Premier League for the first time in their history.
In their first season in the Premier League the club finished fifth. Home matches were initially played at Maccabi Ahi Nazareth's Ilut Stadium, whilst their home ground had floodlights installed. They returned home in February 2005. However, the following season, 2005-06, they finished second from bottom (on goal difference), and returned to Liga Leumit. In 2007-08 they finished bottom of Liga Leumit, and were relegated to Liga Artzit.
Despite only finishing seventh in Liga Artzit in 2008-09, F.C. Nazareth Illit were promoted back to Liga Leumit as restructuring meant the top seven clubs were automatically promoted. Since then, Nazareth Illit hasn't been relegated for 3 consecutive seasons, finishing 7th in 2009-10, 11th in 2010-11 and 12th in 2011-12.
In the 2012-13 season of the league, currently under process, Nazareth Illit is surprisingly at the top of the table. With the joining of players like Ibrahim Basit, Eran Malchin and Moti Malka, Nazareth Illit is ranked 2nd, with 8 fixtures to go in the season. If the team will stay in that position until the end of the season, they will be promoted to the Israeli Premier League for the first time since their relegation in 2006.