The club was founded in 1962. In 1978–79 the club won Liga Alef North division and was promoted to Liga Artzit, then the second tier. 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.