Two seasons later, under Polish manager Wojciech Łazarek, Tayibe won the Liga Artzit title, finishing 15 points clear of third-placed Hapoel Bat Yam,[3] and were promoted to Liga Leumit, the top division, becoming the first Israeli Arab club to play at the top level in Israel.

Lazarek was replaced by Zvi Rosen in January, and then Rifaat Turk, but despite the changes in management Tayibe finished bottom of the table, resulting in relegation back to Liga Artzit.

Back in the second tier, Tayibe finished eighth in the 1997–98 season, in which their match against fellow Arab club Bnei Sakhnin had to be abandoned due to fans rioting.

[8] In their first season back at the fourth level, the club finished bottom of the north division of Liga Alef, and were relegated again.

In the same season Bnei Sakhnin and another Arab club, Maccabi Ahi Nazareth, were both promoted to the top division.