レッドスター・ベオグラード
1945年 - 1965年
第二次世界大戦中の1945年3月4日、レッドスターは反ファシズムを標榜する若者たちの集団による内務省系の総合文化クラブとして設立された。クラブは主将としてBSKベオグラードで活躍をしていたライコ・ミティッチを迎え入れ、終戦後の1946年からユーゴスラビアリーグに参加する。
1948年から1950年まで3年連続でユーゴスラビアカップを優勝したクラブのリーグ初優勝は1951シーズンであった。1955年には前年王者ハイデュク・スプリトの中心選手だったヴラディミル・ベアラやドラゴスラヴ・シェクララツなどを獲得。後に星人（後述）の称号を得るミティッチ、シェクララツを始め、幾人もの代表選手が顔を揃えたクラブは、このシーズンからリーグ4連覇を達成するなど国内では無類の強さを見せ、1950年代は6回のリーグ優勝、2回のカップ優勝を記録した。
欧州の舞台に初めて姿を見せたのは、1956-57シーズンのチャンピオンズカップ（UEFAチャンピオンズリーグの前身大会）であった。この大会ではオランダのラピッドJC、ブルガリアのCDNAソフィアを破り準決勝まで勝ち進むが、準決勝では得点を奪えないままイタリアのフィオレンティーナに敗れた。2年後の1958-59シーズンはルクセンブルクのスタッド・デュドランジュを相手に当時の最多得点記録となる2試合計14対1の大差で勝利するものの、準々決勝でイングランドのマンチェスター・ユナイテッドに敗れた。
1960年代に入ると50年代までの強さは影を潜め、3シーズン連続で無冠に終わる。1962-63シーズンはクラブ史上最低順位となる7位に低迷し、得点数は降格争いをしていたヴォイヴォディナ・ノヴィサドの半数以下であった。
1966年 - 1985年
1966年ミリャン・ミリャニッチが監督に就任し、世代交代を推し進めた。クラブの中心だったシェクララツはドイツへ去り、後に「第3の星人」の栄誉を受け、UEFAジュビリーアウォーズにて過去半世紀におけるセルビア史上最高の選手と称えられる左サイドのウインガー、ドラガン・ジャイッチが台頭した。就任初年度は5位に低迷するものの、1967-68シーズンからリーグ3連覇を達成。1970-71シーズンには再びチャンピオンズカップの準決勝まで進出したが、ギリシャのパナシナイコスFCの前に4対4のタイスコアながらアウェイゴールの差で敗れた。ミリャニッチは1974年、レアル・マドリードに引き抜かれるまで指揮を採り、4度のリーグ優勝、3度のカップ優勝を成し遂げた。
ミリャニッチ辞任の翌年にジャイッチはクラブを去り、ヴラディミル・ペトロヴィッチの時代が始まった。1972年6月にデビューしたペトロヴィッチは「ピジョン（鳩）」のニックネームを授かり、1970年代後半に入るとクラブの絶対的なエースへと成長した。1978-79シーズンのUEFAカップでは、このシーズンリーグ得点王に輝いたドゥシャン・サヴィッチらと共にクラブを初のUEFA主催大会決勝へ導き、後に「第4の星人」として表彰された。ペトロヴィッチは1982年にクラブを去るが、以降もトミスラヴ・イヴコヴィッチ、ボシュコ、ミルコのジュロヴスキ兄弟などのユーゴスラビア代表選手が活躍し、ミリャニッチ辞任後の10年で2強を形成していたライバル、パルチザンを上回る4回のリーグ優勝を飾った。
1986年 - 1991年
1986年、復帰したジャイッチを始めとするフロント陣は5年に渡る長期計画を立て、欧州制覇という大目標を掲げる。そしてジャイッチに才能を見いだされ、「ピクシー（妖精）」ドラガン・ストイコビッチが入団したのもこの年であった。1987年の夏より5ヶ年計画は始まった。
1987年のクラブが誕生した日、レッドスターはレアル・マドリードにマラカナで敗れた。この日から1992年の3月までの5年間、レッドスターは黄金時代と言える最良の時間を過ごした。ロベルト・プロシネチキ、シニシャ・ミハイロヴィチ、デヤン・サビチェビッチなどユーゴスラビアを代表する選手が顔を揃え、国内リーグでは5シーズンで4度の優勝を飾った。ストイコビッチは3年連続でMVPを獲得するなど大活躍し、1990年にクラブを去った。この5年間で監督は5人変わったが、フロント陣の顔ぶれに変わりはなかった。
1990年4月から5月にかけてユーゴスラビア各地で初の自由選挙が行われ、連邦を構成する各共和国で独立の機運が高まっていた。5月13日、ザグレブで行われた対ディナモ・ザグレブとの試合で暴動が起こり、これをきっかけにユーゴスラビア全土に戦火が広がっていくことになる（詳細は1990年ディナモ・ザグレブ対レッドスター・ベオグラード戦での暴動を参照）。
1990-91シーズンのチャンピオンズカップでは、フランスのオリンピック・マルセイユをPK戦の末に破り初の欧州王者となる。皮肉にも前年までクラブに多大な貢献をしてきた「第5の星人」ストイコビッチはマルセイユのベンチを暖めていた。試合を決めるPKを蹴ったダルコ・パンチェフはこのシーズンのヨーロッパ・ゴールデンシューを獲得した。その後のインターコンチネンタルカップでもチリのコロコロを破り世界一となり、このときの「セルビアを東京へ」というスローガンは、その後のユーゴスラビア紛争でも多用された。
1992年 - 現在
長引く紛争に国連による制裁など、欧州王者となったクラブを取り巻く状況は苦しいものとなっていく。前回大会王者として臨んだ1991-92シーズンのチャンピオンズカップでは、ホームゲームは全て第3国での開催となり、この大会から導入されたグループステージでイタリアのサンプドリアに及ばず敗退した。主だった戦力は西側諸国に流出し、ユーゴスラビアは解体された。
紛争終了後の新生ユーゴスラビアリーグでは、ダルコ・コバチェビッチやデヤン・ペトコヴィッチ、ネボイシャ・クルプニコビッチなどの新しい力がコンスタントに台頭するも、ほとんどのシーズンでパルチザンの後塵を拝する結果となった。監督は次々に更迭され、星人ピジョン・ペトロヴィッチまでもが1年を待たずに職を追われた。紛争終了後のリーグ優勝は1999-00シーズンまで無く、1990年代を通じてリーグ優勝は2回に留まった。
1998年にはジャイッチが、2005年にはストイコビッチが会長に就任し、2009年には再びペトロヴィッチが監督として復帰した。2000年代に入っても国内リーグではパルチザンとの2強を形成しているが、2009年は所属選手の給与未払いが表面化するなど、2500万ドルに上るとも言われる負債による財政難もあって、欧州の舞台では活躍できない日々が続いている。
2010年、クラブは新たなメインスポンサーとしてロシアのガスプロム社と5年の契約を結んだ。契約料は年間380万ドルと報道されている。
スタジアム
ホームスタジアムであるスタディオン・ツルヴェナ・ズヴェズダは1963-64シーズンから使用が開始された。3年の工期を経て建設された収容人員5万人を超す巨大スタジアムは、当時のバルカン諸国最大規模を誇った。スタジアムのこけら落としは1963年9月1日、NKリエカとの対戦で、試合はレッドスターが2対1で勝利した。翌年、スタジアムには11万人もの観衆が押し寄せ、その光景は世界最大のスタジアム、エスタジオ・ド・マラカナンを連想させた。これ以降、スタジアムは「マラカナ」の通称で呼ばれることとなる。このシーズン、レッドスターは4季ぶりにリーグ優勝を果たした。
現在の収容人員は55,000人程で、マラカナの北西に位置するパルチザンの本拠地スタディオン・パルチザンとは直線距離にして約1キロ程しか離れていない。