Baigiantis II pasauliniam karui, 1945 m. surengtame Albanijos čempionate žaidė dvi karinių divizionų komandos – Škoderio Ylli Shkodra ir Korčės Liria Korça. Pasibaigus sezonui jos abidvi iširo, o žaidėjai perėjo į Tiranoje sukurtą „Ushtria“ (albaniškai „armija“) komandą.[1]
1946 m. sausio 13 d. ši komanda sužaidė pirmąsias savo rungtynes – varžovas buvo Vllaznia Shkoder, o dvikova baigėsi be įvarčių 0-0. Komanda žaidė raudona apranga. Vasario 4 d. komanda persivadino partizanų garbei „Partizani“ ir pirmąsias rungtynes naujuoju vardu sužaidė balandžio 7 d. su 17 Nentori Tirane klubu, kurias laimėjo 2-0. 1946 m. komanda Albanijos pirmenybėse nežaidė, bet debiutavo 1947 m. ir iškart laimėjo aukso medalius. Savo sėkmę komanda pakartojo 1948 ir 1949 m.
Komunistų valdymo laikais „Partizani“ komandą rėmė vidaus reikalų ministerija ir buvo pavaldi kariuomenei.[2] Per tą laiką komanda 14 kartų laimėjo Albanijos čempionatą. Tačiau po 1990 m. klubas buvo privatizuotas ir iki 2024 m. vos triskart tapo šalies čempionais.