Klub został założony w 1979 roku przez Albańczyków z Tetowa. Celem było stworzenie klubu, któremu mogliby kibicować Albańczycy mieszkający w Jugosławii. Na klub negatywnie patrzyły władze Jugosławii i ostatecznie zakazały mu uczestnictwa w lidze. Mówiono, że klub mógł wzbudzić nacjonalistyczne nastroje wśród jugosłowiańskich Albańczyków. Po proklamacji niepodległości Macedonii klub został reaktywowany i startował w mistrzostwach Macedonii. W sezonach 1996/97, 2000/01 oraz w latach 2004-2008 występował w I lidze. W sezonie 2009/2010 zajął pierwsze miejsce w II lidze i powrócił do I ligi. W pierwszym swoim sezonie 2010/2011 zdobył mistrzostwo Macedonii.
Šhkendija konkuruje z większością klubów macedońskich, szczególnie z Wardarem Skopje i Teteksem Tetowo. Derby Šhkendija - Teteks są największymi w Macedonii.
Q – runda eliminacyjna, 1/16, 1/8, 1/4, 1/2 – odpowiednia faza rozgrywek, Grupa – runda grupowa, 1r gr – pierwsza runda grupowa, 2r gr – druga runda grupowa, F – finał, R – runda, PO – play-off
k. – rzuty karne, los. – losowanie, Dogr. – dogrywka, w. – zasada bramek strzelonych na wyjeździe