De club werd in 1979 opgericht door etnische Albanezen uit Tetovo en promoveerde in 1996 voor het eerst naar de hoogste klasse. Na een seizoen werd de club echter weer naar de tweede klasse doorverwezen. In 2000 keerde de club terug en werd twaalfde op veertien clubs, doordat de competitie naar twaalf clubs werd herleid moest Shkendija degraderen. Na twee seizoenen promoveerde de club opnieuw en kon dit keer standhouden. In het eerste seizoen werd de club vijfde en haalde die plaats ook het volgende seizoen. In 2008 degradeerde de club. Na twee seizoenen promoveerde de club weer. In 2011 behaalde Shkendija het grootste succes in de historie door landskampioen te worden. Hiermee ging de club dan ook voor de eerste keer Europees voetbal spelen.
Jeton Bekjiri
Zie Lijst van Europese wedstrijden van FK Shkëndija 79 Tetovo voor het hoofdartikel over dit onderwerp.
· 
· 