Klubas įkurtas 1945 m. Kitados rungtyniavo Jugoslavijos aukščiausioje lygoje, vėliau – Serbijos ir Juodkalnijos čempionate, o galutinai subyrėjus Jugoslavijai, žaidė Serbijos čempionate. Daugkartiniai Serbijos čempionai ir futbolo taurės laimėtojai. Atstovavo šaliai Europos žemyno turnyruose.
2018 m. vasarą Čempionų lygos atrankose kovojo prieš Marijampolės „Sūduva“. Serbijoje rezultatu 3-0 nugalėjo „raudonosios žvaigždės“, o Lietuvoje dar kartą pergalę šventė serbų klubas (2-0). Bendras rezultatas buvo 5-0, serbų klubo naudai.