FK Crvena zvezda rozgrywa mecze domowe na stadionie noszącym imię Rajka Miticia, kapitana i napastnika, który poprowadził wielkie pokolenie lat 50. Ta drużyna dotarła do półfinału Pucharu Europy w 1957 roku, gdzie uległa Fiorentinie, oraz do ćwierćfinału w 1958 roku, w którym odpadła z Manchesterem United po wyniku 4:5 w dwumeczu. W rewanżu rozegranym w Belgradzie 5 lutego 1958 roku Crvena zvezda odrobiła straty z 0:3 i zremisowała 3:3, ale dalej awansował United, który wygrał pierwszy mecz 2:1. Było to ostatnie spotkanie „Busby Babes”, których samolot rozbił się w Monachium w drodze powrotnej następnego dnia.
Klub został założony 4 marca 1945 roku. Przejął stadion i czerwono-białe barwy nieistniejącego już SK Jugoslavija, a te barwy do dziś stanowią o jego tożsamości. Obecny obiekt otwarto 1 września 1963 roku w miejscu dawnego stadionu Jugoslavii, meczem wygranym z Rijeką 2:1. W 2014 roku nadano mu imię Miticia (1922–2008). Kibice nazywają go „Marakaną”, a w 1973 roku odbył się tu finał Pucharu Europy, w którym Ajax pokonał Juventus 1:0.
Europejska historia klubu obejmuje także inne ważne epizody. W sezonie 1973/74 Crvena zvezda wyeliminowała Liverpool w drugiej rundzie Pucharu Europy, a w 1971 roku dotarła do kolejnego półfinału, w którym odpadła z Panathinaikosem po bramkach na wyjeździe po remisie 4:4 w dwumeczu. W 1979 roku zagrała w pierwszym europejskim finale, w Pucharze UEFA, przegrywając 1:2 w dwumeczu z Borussią Mönchengladbach.
Absolutny szczyt przyszedł w 1991 roku. W drodze do finału drużyna trenera Ljupki Petrovicia wyeliminowała w półfinale Bayern Monachium, wygrywając 2:1 w Monachium i remisując 2:2 w Belgradzie. 29 maja 1991 roku na stadionie San Nicola w Bari pokolenie z Dejanem Savićeviciem, Robertem Prosinečkim, Sinišą Mihajloviciem, Darko Pančevem i Miodragiem Belodediciem zmierzyło się z Olympique Marsylia. Mecz zakończył się bezbramkowym remisem po dogrywce. W serii rzutów karnych pierwszy strzał Marsylii, oddany przez Manuela Amorosa, obronił kapitan i bramkarz Crvenej zvezdy Stevan Stojanović, po czym wszystkie następne rzuty zostały wykorzystane, a Crvena zvezda wygrała 5:3, przy czym decydującego karnego strzelił Pančev. Została pierwszym jugosłowiańskim klubem, który zdobył Puchar Europy, i dopiero drugim ze wschodniej Europy po Steaule Bukareszt w 1986 roku. W grudniu 1991 roku dołożyła Puchar Interkontynentalny w Tokio, pokonując chilijskie Colo-Colo 3:0, dzięki czemu jest jedynym jugosłowiańskim klubem, który został mistrzem świata.
Na krajowym podwórku Czerwona Gwiazda pozostaje siłą dominującą. Sezon 2025/26 przyniósł dziewiąty z rzędu tytuł mistrza Serbii i, według rachunku samego klubu, 37. mistrzostwo kraju w historii, przypieczętowane w kwietniu 2026 roku zwycięstwem 3:0 nad Partizanem w Wiecznych Derbach. W tym samym sezonie klub zdobył też Puchar Serbii, jego 30. w historii, kompletując szósty z rzędu dublet ligowo-pucharowy. Między kwietniem 2017 a grudniem 2025 roku nie przegrał 159 kolejnych meczów ligowych u siebie, a serię przerwała dopiero porażka 0:1 z Vojvodiną 7 grudnia 2025 roku.
Atmosferę wokół klubu współtworzy grupa kibiców Delije oraz Wieczne Derby z Partizanem, jedno z najgorętszych spotkań w europejskim futbolu. Dla Czerwonej Gwiazdy triumf z 1991 roku w Bari pozostaje punktem odniesienia, z którym porównuje się każdy kolejny sezon.