Klub je osnovan 1947. Osvojio je Kup Jugoslavije 1961. pobijedivši u finalu Varteks Varaždin 2:1. U Europskom kupu pobjednika kupova 1961./62. eliminirao ga je u osmini finala škotskiDunfermline Athletic. Svoje najbolje trenutke klub je doživljavao 1987., kada je ekipa predvođena Darkom Pančevom, Ilijom Najdoskom, Draganom Kanatlarovskim, Čedomirom Janevskim i Vujadinom Stanojkovićem osvojio Prvu saveznu ligu Jugoslavije 1986./87. Osvajanjem tog prvenstva, FK Vardar je postao jedini makedonski klub, koji je osvojio odličje prvaka Jugoslavije, što su u to vrijeme mogli samo: zagrebačkiDinamo, splitskiHajduk i beogradskiPartizan i Crvena zvezda. Vardar je imao 1 bod prednosti pred Partizanom i 9 bodova pred ostalim klubovima, zbog toga što je početkom te sezone otkriveno da su neke utakmice bile namještene u prethodnoj sezoni 1985./86. Stoga su se nekim klubovima oduzeli bodovi. Naslov je kasnije (1988.) dan Partizanu, jer je Partizan pobijedio u sporu koji se vodio pred jugoslavenskim ustavnim sudom. Ipak, Vardar je u sezoni 1987./88. predstavljao Jugoslaviju u Kupu prvaka.[1] Već u 1. krugu, Vardar je izgubio od portugalskogPorta. Nakon raspada Jugoslavije i stvaranja makedonske lige, Vardar je uvijek bio dominantan klub, te je uzastopno osvojio 3 makedonska prvenstva i 2 makedonska kupa. Iako je nakon toga (u sljedećih 6 godina) klub oslabio, i tada su osvojena 2 kupa. Klub se počeo oporavljati ponovnim dolaskom trenera Gjoka Hadžievskog, s kojim su osvojena još dva odličja.