The club was founded in 1962 as Hapoel Kiryat Nazareth and competed in Liga Gimel for several seasons, before promoting to Liga Bet at the end of the 1971–72 season. In 1973, after Nazareth Illit was granted city status and officially changed its name.
In 1998-99 the club finished as runners-up in Liga Alef North, and was 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 top division 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.