De club werd in 1937 als Volga 1937 Skopje opgericht en fuseerde in 1945 met Radnički 1938 Skopje en Sloboda 1940 Skopje en werd zo FK Rabotnitsjki Skopje. In 1951 promoveerde de club naar de hoogste klasse van Joegoslavië. Na één seizoen degradeerde de club. Rabotnički vond na één seizoen opnieuw aansluiting bij de elite maar kon ook nu niet standhouden. Daarna zou de club nooit meer weerkeren en was vooral in de tweede klasse actief.
Na de onafhankelijkheid van Macedonië duurde het tot 1998 vooraleer de club naar de hoogste klasse kon promoveren onder de naam FK Rabotnitsjki Kometal Skopje. Nadat het bedrijf Kometal de club overnam ging het steeds beter met de club. In 2002 eindigde de club op vierde plaats, die plaats haalde de club ook de volgende twee seizoenen. In 2005, 2006 en 2008 werd de club landskampioen en in 2008 en 2009 werd zowel de nationale beker veroverd. In 2008 werd de sponsornaam Kometal weggelaten in de naam.