Disputa le sue partite casalinghe allo stadio Gjorče Petrov, che ha 3 000 posti a sedere. I colori sociali sono il giallo e il rosso.
Storia
Fondato nel 1932 come H.A.S.K., il club ha assunto negli anni le denominazioni di Pagna, Rudar, Industrijalec e Jugokokta, per poi prendere il nome attuale nella stagione 1989-1990 per commemorare Gjorče Petrov, un rivoluzionario considerato figura chiave del movimento nazionale macedone.
Il Makedonija entrò nella Prva liga, la massima serie del campionato macedone, quando essa fu costituita, nel 1992, data d'indipendenza della Macedonia dalla Jugoslavia. La squadra retrocesse nella Vtora liga, la seconda divisione nazionale, al termine della stagione 1993-1994. Dopo una sola stagione in seconda divisione, fece ritorno in Prva liga.
Nella stagione 1997-1998 chiuse terza e si qualificò per la prima volta alla Coppa Intertoto, dove superò al primo turno gli sloveni dell'Olimpia Lubiana, ma fu eliminata al secondo turno dai francesi del Bastia.
Nella stagione 2001-2002 retrocesse di nuovo e rimase poi per tre anni in seconda serie. Al termine della stagione 2004-2005 tornò in Prva Liga grazie al terzo posto in classifica, mentre nell'annata 2005-2006 chiuse al secondo posto in massima divisione e colse il primo successo aggiudicandosi la Coppa di Macedonia. Nel 2006-2007 giocò in Coppa UEFA, dove fu eliminata dal Lokomotiv Sofia. Nel 2008-2009 perse la finale di Coppa di Macedonia, ma vinse per la prima volta il campionato, con sei punti di vantaggio sul Milano Kumanovo, qualificandosi così ai preliminari di UEFA Champions League.
Non essendosi presentata in campo per più di due partite consecutive, nel 2009-2010 la squadra fu declassata in seconda serie per aver boicottato il campionato di Prva liga insieme ad altre due compagini, cui toccò la stessa condanna. Tornò a giocare solo nella stagione 2011-2012, in Vtora liga, dove chiuse al quarto posto. Nel 2012-2013 ottenne la promozione in massima serie vincendo la Vtora liga , ma l'anno dopo vi fu una nuova retrocessione a causa del decimo posto in Prva liga. Il ritorno in massima serie fu ottenuto al termine del campionato 2015-2016 di Vtora liga, ma il club retrocesse dalla massima serie alla fine della stagione 2016-2017, piazzandosi decimo. Chiuso il campionato di seconda divisione 2017-2018 al primo posto, fu promosso nuovamente in massima serie, dove chiuse quinto l'anno dopo, perdendo nello stesso anno la finale della coppa nazionale.
