De club werd in 1941 opgericht en was vrij succesvol in het Macedonische voetbal ten tijde van Joegoslavië. Pelister werd kampioen van Macedonië in 1960, 1961, 1975 en 1982. Dit was natuurlijk geen eerste klasse voetbal maar een lagere divisie in de Joegoslavische competitie, de kampioen speelde dan een play-off om naar de Joegoslavische 2de klasse te promoveren. Daar werd de club 6de in 1991, omdat de Kroatische en Sloveense clubs zich terugtrokken uit de hoogste klasse (zes clubs in totaal) en een eigen competitie opzetten promoveerde Pelister naar de hoogste klasse en werd daar 15de, het liet gerenommeerde clubs als Spartak Subotica, Sloboda Tuzla en Zeljeznicar Sarajevo achter zich. Na dit seizoen trokken ook de Macedonische clubs zich terug uit de competitie.
Na de onafhankelijkheid van Macedonië was de club medeoprichter van de hoogste klasse en werd meteen vierde. Ook de volgende drie seizoenen eindigde Pelister in de topvijf. Na een 11de plaats in 1997 herpakte de club zich weer in 1998 met een 6de plaats. De volgende seizoenen eindigde de club in de middenmoot, met uitzondering van 2000 toen Pelister vierde eindigde. In 2001 werd de beker gewonnen en speelde de club Europees voetbal. In 2003 degradeerde de club voor het eerst. Na drie seizoenen in de tweede klasse werd de club kampioen en kon terugkeren voor het seizoen 2006/07. In 2011 degradeerde Pelister en keerde een seizoen later weer terug om in 2014 direct weer te degraderen. In 2017 won de club voor de tweede keer in de clubhistorie de Macedonische beker. In de finale versloeg het Shkendija 79 Tetovo na strafschoppen. In 2018 degradeerde de club weer maar keerde in 2020 weer terug op het hoogste niveau.
.svg)
Mitko Stojkovski
Vlatko Kostov
.svg){kind=small}
