Историја фудбалске репрезентације Црвене звезде почела је оснивањем Комитета југословенских комуниста 4. марта 1945. године. Слободан Пенезић је руководио одбором који је основао Црвену звезду, састављен углавном од комунистичких ветерана из Другог светског рата. То је било супротно Партизану, јер су га основали високи генерали и припадници Југословенске народне армије.

Оснивање и прва титула (1945–1951) У фебруару 1945. године, током Другог светског рата, група младића, чланова Српске уједињене антифашистичке омладинске лиге, одлучила је да оснује Омладинско физичко културно друштво, које ће 4. марта постати Црвена звезда Београд. На крају Другог светског рата, неколико предратних југословенских клубова је распуштено јер су играли утакмице током рата и били су означени као колаборационисти од стране комунистичких власти маршала Јосипа Броза Тита. Два од ових клубова из Београда били су Југославија и БСК Београд. Црвена звезда је настала од остатака Југославије и добила је југословенски стадион, канцеларије, играче, па чак и своје црвено-беле боје. Име Црвена звезда клубу је додељено после дуже расправе, а доделили су га први потпредседници спортског друштва Зоран Жујовић и Слободан Ћосић. После бројних предлога, Ћосић је на крају рекао: „Да наше друштво зовемо Звезда?“, а Жујовић је спонтано рекао: „Супер, ако је Звезда, нека буде Црвена звезда“. Са овим предлогом су били сагласни сви присутни, иако је било предлога да се клуб зове Плава звезда. Иначе, Црвена звезда је убрзо усвојена као симбол Србије, спортска институција која је и данас најпопуларнија у земљи.Fifa.com - FK Crvena Zvezda Beograd (Red Star Belgrade) - Red Star claim gold for the Balkan peninsula Тог дана Црвена звезда је одиграла прву фудбалску утакмицу у историји клуба против Првог батаљона Друге бригаде КНОЈ- а и победила резултатом 3 : 0. Пет дана касније формирана је фудбалска секција коју су водили Коста Томашевић и Предраг Ђајић. Њих двојица су бранили част Црвене звезде на терену – Томашевић је био први стрелац и стрелац у историји клуба (који је постигао и први европски гол за Црвену звезду против Рапида током Купа Европе 1956–57), а Ђајић је био снажан везиста. У послератној сезони 1946. године, Црвена звезда је освојила првенство Србије и тако се пласирала у Прву лигу Југославије. У првим сезонама клуб је освојио 3. место и два вицешампиона. Ипак, у периоду од 1948. до 1950. године клуб је постигао серију тријумфа у југословенским куповима, победивши у финалу градског ривала Партизана, Наша крила из Земуна и загребачки Динамо. Звездино освајање прве лигашке титуле је освојено на спектакуларан начин. Три кола пре краја, загребачки Динамо је био пет бодова предности у лиги (победа у мечу донела је клубу тада два бода.) Међутим, загребачки тим је поражен од екипе Сарајева, а Црвена звезда је победила у дуелу ривала за првенство и ушла у последње коло са само једним бодом заостатка. Утакмица између БСК Београда и Динама завршена је нерешеним резултатом 2:2, а првенство је одлучено дан касније, 4. новембра, у утакмици са Партизаном. Вечити ривал Црвене звезде је раније те сезоне веома убедљиво победио у претходном дербију (6 : 1), али је овога пута Звезда произвела потребан резултат 2 : 0 и захваљујући нешто бољем просеку голова први пут је постала првак Југославије.

Касне 1950-те – прва ера доминације (1952–1958) Црвена звезда је освојила првенство и 1953. године, али праве промене уследиле су тек средином деценије, када је формирана стабилна клупска структура са Душаном Благојевићем на месту председника, Слободаном Ћосићем као генералним секретаром и сјајним Ацом Обрадовићем, познатим по надимку Доктор О, на месту техничког директора клуба. Заједно су утрли пут генерацији која ће у потпуности доминирати југословенском и европском фудбалском сценом у наредних пет година. Била је то екипа играча као што су Беара, Дурковић, Станковић, Поповић, Митић, Костић и Шекуларац. Ти фудбалери, чија се имена још памте, освојили су четири југословенска првенства и два Купа, не пропустивши прилику да пет сезона заредом освоје сваки трофеј Југославије. Игра Црвене звезде била је брза и офанзивна, чиме је клуб стекао велику популарност како у земљи тако и у свету. Како су побеђивали на терену, Обрадовић је формирао терен за професионални рад који ће касније послужити као основа бројних успеха клуба. Црвена звезда је 1956. године освојила првенство и изборила полуфинале Купа Европе 1956/57, где је играла против Фјорентине. Нападач Црвене звезде Костић постигао је пет голова на четири досадашње утакмице Купа Европе. И поред Костићеве способности пред голом, Црвена звезда није успела да постигне ниједан гол, па су Италијани прошли у финале. Као шампиони, Црвена звезда је била Југославија која је учествовала у Европском купу 1957–58 где су је славно победили енглески шампион Манчестер јунајтед у четвртфиналу са 5 : 4, а тим којим је управљао Мет Базби победио је Црвену звезду са 2 : 1 у првој утакмици у Енглеској пре него што је ремизирао у реваншу 3 : 3 у фебруару на стадиону Партизана.Red Star Belgrade - Manchester United 3-3 (1958) Реванш је значајан по томе што је то последња утакмица коју су играле "Базбијеве бебе". На повратном лету за Енглеску следећег дана, авион се срушио у Минхену, што је резултирало смрћу 23 особе, укључујући осам играча Манчестер јунајтеда. Црвена звезда је 1958. године освојила и свој први европски трофеј, Митропа куп, који се играо током лета, у паузи између сезона. Трофеј је освојен без изгубљене утакмице.

Криза и нови стадион Црвене звезде (1958–1966) десно|мини|240x240п|Стадион Рајко Митић, познат као "Маракана" Крај педесетих је био први период доминације једног клуба на југословенској фудбалској сцени, али се почетком следеће деценије тежиште дешавања померило на другу страну Топчидерског брда, где се налазио Партизан. У наредних седам сезона Црвена звезда је успела да освоји само једно првенство и само један пехар, што није било довољно за клуб од Звездиног стаса и амбиција. Његов пласман током ових сезона био је најгори у његовој историји (укључујући и седмо место 1963.). Црвена звезда је чак четири пута пала испод прве три на табели (пре и после тога, Црвена звезда никада није пала испод трећег места у 54 фудбалске сезоне у СФРЈ, СРЈ, СЦГ и Србији). Већ тада је било јасно да је Црвена звезда убедљиво најпопуларнији клуб у земљи, а њени порази тешко су падали навијачима. Тако су присталице Црвене звезде у неким приликама имале тенденцију да упадну на терен и буквално спале обе стативе. У сезони 1963. клуб је успео да постигне само 21 гол, што је, на пример, упола мање од Војводине, иако је на табели завршила пет места ниже.

С друге стране, Црвена звезда је остварила добре резултате на међународној сцени. У Купу сајамских градова 1961–62, Црвена звезда је елиминисала Еспањол у четвртфиналу, а за полуфинале Црвена звезда је морала да игра против Барселоне. У оба меча Барселона је била боља и Црвена звезда је испала. Међутим, само осам месеци касније, каталонски клуб је поражен од Црвене звезде у истој фази истог такмичења. Али чак ни победа против Роме од 2 : 0 није била довољна за Црвену звезду да напредује.

Поред међународних успеха, Црвена звезда наставља да се развија, а изградња новог стадиона започета је у Београду крајем 1959. године. У наредне четири године Црвена звезда је играла домаће утакмице на Партизановом стадиону и на стадиону ОФК Београда (ово се може сматрати једним од разлога лоших резултата које је остварила у овом периоду). Нови стадион је отворен 1963. године и Црвена звезда је играла против Ријеке, а временом је распродати стадион Црвене звезде добио незванични назив „Маракана“, по чувеном стадиону Маракана у Бразилу, а стадион је стекао репутацију веома тешког терена за играње гостујућих екипа. У првој сезони постојања стадиона, Црвена звезда је славила освајањем дупле круне, док их је Милорад Павић водио до ових победа. Кључни тренутак догодио се 1966. године, када је Миљан Миљанић постао тренер клуба. У наредних осам година, Миљанић је трансформисао Црвену звезду у високо оцењену европску екипу. Југословенски фудбал је до тада прошао кроз уводну фазу тестирања и наставила се доминација Црвене звезде и Партизана. У преосталих 25 година постојања Југославије, Црвена звезда би остала стални трофејни фаворит, мењали би се само противници. Црвена звезда је 1968. године освојила свој други трофеј Митропа купа и после освајања Црвена звезда се повукла из Митропа купа како би се више фокусирала на друга европска такмичења.

Миљанићево доба (1966–1975) Прошавши кроз омладински систем клуба, Миљан Миљанић је током раних 1950-их година неколико пута наступао за комплетан тим Црвене звезде пре него што је без церемоније окончао своју скромну фудбалску каријеру; међутим, деценију и по касније, у лето 1966, када је почео да тренира, почео је да бележи успехе. У првој сезони на месту селектора Црвене звезде, Миљанић је потпуно променио клупски састав и завршио на петом месту у лиги, као и претходне сезоне под претходним тренером Иваном Топлаком.

Следеће сезоне, генерација предвођена двадесетједногодишњим Драганом Џајићем — који је наставио сјајну фудбалску каријеру, званично проглашен за најбољег српског играча икада и генерално сматран једним од најбољих левих крила у светском фудбалу — почела је да оставља дубок траг у југословенском и српском фудбалу. Са играчима као што су Ратомир Дујковић, Милован Ђорић, Кирил Дојчиновски, Станислав Караси, Јован Аћимовић, Војин Лазаревић, Петар Кривокућа, Стеван Остојић и Бранко Кленковски, период 1967—1970. је био први пут да је Црвена звезда успела да освоји три узастопне лигашке титуле и две узастопне дупле круне. Истовремено, Црвена звезда је постала успешан и доследан извођач и на европској сцени. Фокусирање на Куп Југославије 1971. довело је до тога да је клуб постигао други најгори пласман у лиги икада – шесто место – међутим, тај утисак је поправљен освајањем купа. Црвена звезда је освојила и два Суперкупа 1969. и 1971. године. Поред победе у купу, Црвена звезда се пласирала и у полуфинале Купа Европе 1970–71, где је елиминисана од грчког Панатинаикоса. У првом мечу, Црвена звезда је, уз бучну београдску публику, победила Грке са 4 : 1 пред 100.000 гледалаца и изгледало је као да је у неприкосновеној позицији,Red Star Belgrade – Panathinaikos 4:1 (1971) све док није пала са 3 : 0 у Атини и тако изгубила на основу гола у гостима и поново пропустила финале. Миљанић је са тимом освојио још један Куп Југославије 1973. Појавили су се неки нови играчи попут Владимира и Огњена Петровића, Богићевића, Филиповића, Јанковића и Керија.