De club werd in 1932 opgericht als HASK, er werd enkele keren van naam veranderd, eerst in Rudar en dan in Industrijalec. Tijdens de Tweede Wereldoorlog speelde de club twee seizoenen in de Bulgaarse competitie. In 1941 werd de club in de eerste ronde uitgeschakeld door Sportklub Plovdiv. Makedonija had de heenwedstrijd gewonnen en verloor de terugwedstrijd waardoor er verlengingen gespeeld werden. Nadat de scheidsrechter een speler van Makedonija van het veld stuurde in de achtste minuut van de verlenging verlieten de spelers het veld en werd SK een 0-3 overwinning toegekend. In de beker (Tsaars Cup) werd de halve finale gehaald. In 1942 nam de club weerwraak op Plovdiv en won met 2-0, na ook JSK Sofia (het latere Lokomotiv) en Slavia Sofia uit te schakelen verloor de club in de eindstrijd van het machtige Levski Sofia met 0-2, 0-1. In 1970 werd de naam in Yugokokta veranderd en speelde de club in de lagere klassen van Joegoslavië. De naam Gorce Petrov werd in 1989 aangenomen.
Na de onafhankelijkheid van Macedonië was de club medeoprichter van de hoogste klasse en degradeerde na twee seizoenen. Na één jaar keerde de club terug en werd een middenmoter en in 1998 werd de derde plaats behaald. Nadat de club in 2001 nipt aan de degradatie ontsnapte moest men in 2002 opnieuw een stap terugzetten. Na twee zevende plaatsen in de tweede klasse werd de club derde in 2005 en promoveerde na het spelen van play-off wedstrijden. In het seizoen 2008/09 werd Makedonija voor het eerst landskampioen. Tijdens seizoen 2009/10 trad de club samen met Sloga Skopje twee keer op rij niet aan als protest tegen de voetbalbond. Hierop werden Makedonija en Sloga uit de competitie gezet en beide clubs degradeerden.
De club staakte de activiteiten en de eigenaren namen derdeklasser FK Treska (opgericht in 1982 als FK Shishevo) uit het naburige Shishevo over. De club ging in het Gorce Petrov Stadion spelen promoveerde in 2011 direct naar het tweede niveau. In januari 2012 stond de bond een naamswijziging toe naar FK Makedonija Gjorce Petrov 1932 waardoor de naam Makedonija terugkeerde. In 2013 werd de club kampioen in de Vtora Liga en promoveerde weer naar het hoogste niveau maar degradeerde direct weer terug. Ook in het seizoen 2016/17 speelde de club op het hoogste niveau maar degradeerde weer.
Naci Şensoy
· 
· 