FKツルヴェナ・ズヴェズダ

1945-1965

第二次世界大戦中の1945年3月4日、レッドスターはユーゴスラビア反ファシスト青年連合同盟（USAOJ）セルビア支部のメンバーによって総合スポーツクラブとして創設された。レッドスターのサッカー部門は戦前の名門クラブだったSKユゴスラヴィヤの資産を受け継ぎ、ユゴスラヴィヤとBSKの選手によって構成され、終戦後の1946年からユーゴスラビアリーグに参加した。

キャプテンとしてクラブを牽引した「チカ」ことライコ・ミティッチを中心に1948年から1950年まで3年連続でユーゴスラビアカップを優勝したクラブのリーグ初優勝は1951シーズンであった。1955年には前年王者ハイドゥク・スプリトの中心選手だったヴラディミル・ベアラやドラゴスラヴ・シェクララツなどを獲得。後に「第1の星人」となるミティッチと「第2の星人」となる「シェキ」ことシェクララツを筆頭に多くの代表選手が顔を揃えたクラブはこのシーズンからリーグ4連覇を達成するなど国内では無類の強さを見せ、1950年代は6回のリーグ優勝と2回のカップ優勝を記録した。

欧州の舞台に初めて姿を見せたのは、1956-57シーズンのUEFAチャンピオンズカップ（UEFAチャンピオンズリーグの前身）であった。この大会ではオランダのラピドJCケルクラーデ、ブルガリアのCDNAソフィアを破り準決勝まで勝ち進むが、準決勝では得点を奪えないままイタリアのフィオレンティーナに敗れた。2年後の1958-59シーズンはルクセンブルクのスタッド・デュドランジュを相手に当時の最多得点記録となる2試合計14対1の大差で勝利するものの、準々決勝でイングランドのマンチェスター・ユナイテッドに敗れた（第2戦終了後にミュンヘンの悲劇が発生した）。

1960年代に入ると50年代までの強さは影を潜め、3シーズン連続で無冠に終わる。1962-63シーズンはクラブ史上最低順位となる7位に低迷し、得点数は降格争いをしていたヴォイヴォディナ・ノヴィ・サドの半数以下であった。

1966-1985

1966年にミリャン・ミリャニッチが監督に就任し、世代交代を推し進めた。クラブの中心だったシェクララツは去り、後に「第3の星人」の栄誉を受け、UEFAジュビリーアウォーズにて過去半世紀におけるセルビア史上最高の選手と称えられる左サイドのウィンガー、「ジャヤ」ことドラガン・ジャイッチが台頭した。就任初年度は5位に低迷するものの、1967-68シーズンからリーグ3連覇を達成。1970-71シーズンには再びチャンピオンズカップの準決勝まで進出したが、ギリシャのパナシナイコスの前に4対4のタイスコアながらアウェイゴールの差で敗れた。ミリャニッチは1974年、スペインのレアル・マドリードに引き抜かれるまで指揮を採り、4度のリーグ優勝、3度のカップ優勝を成し遂げた。

ミリャニッチ辞任の翌年にジャイッチはクラブを去り、ヴラディミル・ペトロヴィッチの時代が始まった。1972年にデビューした「ピジョン」ことペトロヴィッチは1970年代後半に入るとクラブの絶対的なエースへと成長し、1978-79シーズンのUEFAカップ（UEFAヨーロッパリーグの前身）では決勝で西ドイツのボルシア・メンヒェングラートバッハに敗れたもののクラブを準優勝に導き、後に「第4の星人」として表彰された。ペトロヴィッチは1982年にクラブを去るが、以降もトミスラヴ・イヴコヴィッチやボシュコ・ミルコのジュロフスキ兄弟などのユーゴスラビア代表選手が活躍し、ミリャニッチ辞任後の10年で4回のリーグ優勝を飾った。

1986-1991

1986年、ヴェリコ・アレクシッチはスヴェトザル・ミヤイロヴィッチ会長、ヴラディミル・ツヴェトコヴィッチ事務総長、ドラガン・ジャイッチテクニカルディレクターといったレッドスター首脳陣と共に5ヶ年計画を立て、欧州制覇という大目標を掲げる。そしてジャイッチに才能を見いだされ、「ピクシー」ことドラガン・ストイコヴィッチが入団したのもこの年であった。1987年の夏より5ヶ年計画は始まった。

1987年3月4日、スペインのレアル・マドリードにホームで勝利した日から1992年3月4日までの5年間は黄金時代といえる最良の時間となった。ヴラディミル・ユゴヴィッチ、シニシャ・ミハイロヴィッチ、ロベルト・プロシネチュキ、デヤン・サヴィチェヴィッチなどのユーゴスラビア代表にルーマニア代表ながらセルビア人のミオドラグ・ベロデディッチを加え、国内リーグでは5シーズンで4度の優勝を飾った。ストイコヴィッチは3年連続でMVPを獲得するなど大活躍したが、1990年にクラブを去った。この5年間で監督は5人変わったが、首脳陣の顔ぶれに変わりはなかった。

1990年4月から5月にかけてユーゴスラビア各地で初の自由選挙が行われ、連邦を構成する各共和国で独立の機運が高まっていた。5月13日、ザグレブのスタディオン・マクシミールで行われたディナモ・ザグレブとの試合で暴動が起こり、これをきっかけにユーゴスラビア全土に戦火が広がっていくことになる（詳細は1990年ディナモ・ザグレブ対レッドスター・ベオグラード戦での暴動およびユーゴスラビア紛争を参照）。

UEFAチャンピオンズカップ 1990-91ではスイスのグラスホッパー、スコットランドのレンジャーズ、東ドイツのディナモ・ドレスデン、西ドイツのバイエルン・ミュンヘンを次々と破る快進撃で決勝に進出した。1991年5月29日、レッドスターはイタリア・バーリのスタディオ・サン・ニコラで行われた決勝戦でスコアレスのままPK戦までもつれ込んだ末にフランスのオリンピック・マルセイユに勝利しクラブ史上唯一の欧州制覇を成し遂げた。皮肉にも前年までクラブに多大な貢献をしてきた「第5の星人」ストイコヴィッチはマルセイユのベンチを暖めていた。マニュエル・アモロスのPKを止めたステヴァン・ストヤノヴィッチはキャプテンとしてビッグイヤーを掲げ、試合を決めるPKを蹴ったダルコ・パンチェフはこのシーズンのヨーロッパ・ゴールデンシューを獲得した。その後のUEFAスーパーカップでは紛争によってホームで試合を行うことができずイングランドのマンチェスター・ユナイテッドに敗れたものの、インターコンチネンタルカップでチリのコロコロを破り世界一となった。その時に掲げられた「スルビヤ・ド・トキヤ（セルビアを東京へ）」というスローガンはユーゴスラビア紛争で多用されることとなった。

1992-

長引く紛争に国連による制裁など、欧州王者となったクラブを取り巻く状況は苦しいものとなった。前回王者として臨んだ1991-92シーズンのチャンピオンズカップでは、ホームゲームは全て中立国での開催となり、この大会から導入されたグループステージでイタリアのサンプドリアに及ばず敗退した。主だった戦力は西側諸国に流出し、ユーゴスラビアは解体された。

紛争終了後のSRユーゴスラビアリーグでは、ダルコ・コヴァチェヴィッチやデヤン・ペトコヴィッチ、ネボイシャ・クルプニコヴィッチなどの新しい力がコンスタントに台頭するも、ほとんどのシーズンでパルチザン・ベオグラードの後塵を拝する結果となった。監督は次々に更迭され、星人ペトロヴィッチまでもが1年を待たずに職を追われた。紛争終了後のリーグ優勝は1999-00シーズンまで無く、1990年代を通じてリーグ優勝は2回に留まった。

1998年にはジャイッチが、2005年にはストイコヴィッチが会長に就任し、2009年には再びペトロヴィッチが監督として復帰したが、その年に所属選手の給与未払いが表面化するなど、2500万ドルに上るとも言われる負債によって財政難に追い込まれた。

2010年、クラブは新たなメインスポンサーとしてロシアのガスプロム社と5年の契約を結んだ。契約料は年間380万ドルと報道されている。

2017年からRFKグラフィチャルをリザーブチームとしている。