Друга деценија Црвене звезде је била још успешнија од прве декаде. Црвено-бели су освојили пет шампионата, три купа, изграђен је стадион, уследила је премијера на европској сцени, где се наш клуб позиционирао као један од најцењенијих тимова, а 1958. године је освојен и престижни Митропа куп.
У првенству фудбалери Црвене звезде су тријумфовали 1956, 1957, 1959, 1960. и 1964. године, најбољи у купу су били 1958, 1959. и 1964. године. Освојене су и прве две дупле круне (1959. и 1964.), али је остварено и неколико подвига у Европи, као и освајање Митропа купа 1958. године.
Наставио је наш клуб убрзан раст и током друге деценије, па је наредна титула, освојена већ 1956. године. Почетак је био буран. На лидерској позицији су биле честе промене. Звезда и Партизан су се смењивали на врху у пролећном делу, али је преокрет настао у 19. колу, када су Црвена звезда и Војводина играли нерешено у Новом Саду (1:1), док је Жељезничар у Сарајеву победио Партизан 1:0. Црвена звезда је тада заузела прво место и није га испуштала до краја. Одиграли смо 26 мечева, од тога 16 пута победили, осам пута ремизирали и претрпели само два пораза, а укупно смо имали 40 бодова. За Црвену звезду су те сезоне играле њене прве две играчке звезде, Рајко Митић и Драгослав Шекуларац, а на голу је био и велики Владимир Беара.
Успели су црвено-бели да се и наредне сезоне попну на шампионско постоље. У сезони 1956/57 Црвена звезда је пети пут била најбоља у Југославији, а титула је математички обезбеђена већ три кола пре краја, након одиграних 26 утакмица, уз 17 победа, пет нерешених и четири пораза и укупно освојених 39 бодова.
Трећа титула у другој декади освојена је две године касније (1959). Сезона 1958/59 је остала упамћена по великим искушењима, скоковима, падовима и преокретима. Сјајна јесен и промењиво пролеће завршени су ипак слављем црвено-белих. Звездин почетак је био фантастичан у виду четири меча и исто толико победа. Хајдук је “прегажен” са 7:0, а Динамо са 4:0. Недаће су почеле на пролеће. Звезда је у првих седам пролећних кола освојила свега пет бодова и на табели се закомпликовала ситуација. Наш клуб је имао 23 бода, Партизан 23, Војводина 22 и Динамо 20 бодова. Био је то финиш без предаха, са неизвесношћу каква није запамћена у нашим првенствима. Звездин тим је на крају, као уосталом и на почетку првенства, био на висини задатка. Најбољи стрелац са 25 голова је био Бора Костић, а Звезда је са 31 освојеним бодом подигла шампионски пехар.
Успешна је била и 1960. година, када је наш клуб по седми пут био најбољи у Југославији. На крају првенства Црвена звезда је после 22 кола, забележила 15 победа, три нерешена исхода и четири пораза, уз освојена 33 бода. На стадиону ЈНА је 27. септембра 1959. године одигран јубиларни 25. вечити дерби, а Црвена звезда је убедљиво савладала Партизан са 3:0.
Пето првенство у другој деценији постојања црвено-бели су освојили 1964. године са 36 бодова. Због обавезног служења војног рока, Звездина друга звезда Драгослав Шекуларац је одиграо тек неколико утакмица, а диригентску палицу на терену је успешно преузео Војислав Мелић. Такође, на главну сцену су ступили Драган Џајић и Живорад Јевтић. Тада је са Џајићем, трећом Звездином звездом, практично и почела доминација Црвене звезде у југословенском фудбалу.
Као и у претходних десет година, тако и од 1956. па до 1965. некадашњи фудбалери нашег клуба су освојили три купа. У финалном мечу 1958, остварена је убедљива победа против мостарског Вележа са 4:0. Стрелци за Црвену звезду су били Костић у 61. и 71, Борозан у 68. и Рудински у 73. минуту. Трофеј у купу, Црвена звезда је одбранила 1959. године, победивши у финалу Партизан са 3:1, а голове за Звезду су постигли Маравић у 11. и Костић у 57. и 70. минуту. Шездесетих година прошлог века, на сцену је ступила чувена Џајићева генерација, а 1964. године је освојен још један трофеј у купу, укупно шести. На новосаграђеном стадиону Црвене звезде, пред 60.000 гледалаца, у завршној представи је славила Звезда против Динама 3:0. Стрелци су били Прљинчевић у 35, Јевтић у 48. и Џајић у 70. минуту.
Капије новог „фудбалског храма“ званично су први пут отворене 1. септембра 1963. године, на утакмици коју је Звезда играла са Ријеком (2:1), а том мечу присуствовало је 55 хиљада гледалаца, да би рекорд те јесени био забележен у дербију са Партизаном, када је на трибинама било 74 хиљаде душа. Већ наредне године, када је изградња стадиона потпуно завршена, капацитет је износио читавих 110 хиљада гледалаца! Због грандиозности и великог капацитета, навијачи су са правом стадион поредили са тада највећим на свету – „Мараканом“ у Рио де Жанеиру. Од тих дана, па све до данас, то име је остало саставни део приче о Црвеној звезди, а наш вољени стадион је постао синоним успеха и победа!
Звездина европска прича је почела 3. новембра 1956. године, у малом холандском граду Керкраде, смештеном у покрајини Лимбург, на самој немачкој граници. Први противник, у првој рунди Купа европских шампиона 1956/1957 био је шампион Холандије Рапид ЈЦ Херлен. Сам почетак показао је каква будућност очекује наш клуб – после само четири минута Бора Костић је дао први Звездин европски гол, а после много драме и преокрета Антон Рудински је обезбедио победу од 4:3. У реваншу, Звезда је победила лако, 2:0 и обезбедила пролаз у следеће коло.
У фебруару је Звезду чекао ЦДНА из Софије (данашњи ЦСКА), који је у Београду био на прагу катастрофе, када је Звезда победила са 3:1, да би у Софији наш клуб доживео први европски пораз од 2:1, међутим то није зауставило наш тим. Већ у првом покушају Звезда је стигла до полуфинала Купа европских шампиона. Трећег априла у Београду је гостовао италијански шампион – Фиорентина. После жестоке борбе меч је одлучен само три минута пре краја, када је Маурилио Прини успео да савлада Кривокућу. У реваншу поново су две екипе биле потпуно равноправне, а голова није било.
У сезони 1957/58 Звезда се поново такмичила у Купу европских шампиона, а у првој рунди декласиран је луксембуршки Стад Диделанж (5:0 и 9:1, уз шест голова Боре Костића). Уследили су мечеви са шведским Норчепингом. Прво смо на гостујућем терену одиграли нерешено (2:2), а затим смо у Београду славили са 2:1. У четвртфиналу су црвено-беле чекале Безбијеве бебе, најталентованија генерација у историји британског фудбала, која је процветала истовремено кад и Звезда. У првом мечу, 14. јануара, Звезда је испустила предност и изгубила 2:1, а реванш се играо 5. фебруара 1958 у Београду. У једној од најузбудљивијих партија у историји еврокупова два гола Бобија Чарлтона донела су Енглезима предност од 0:3 на полувремену, али су Костић и Тасић вратили наш тим на 3:3 већ у 58. минуту. После пола сата потпуне драме резултат је остао непромењен, а пласман у полуфинале изборио је Манчестер јунајтед.
Фудбалери две екипе провели су вече у пријатном дружењу, не слутећи шта ће се десити већ следећег дана. При повратку у Енглеску авион са експедицијом Манчестер јунајтеда срушио се на минхенском аеродрому. Погинула је 21 особа, међу којима и осам првотимаца Манчестер јунајтеда. Једна од најтежих несрећа у историји светског фудбала заувек је зближила два велика фудбалска клуба.
У сезони 1960/61, је већ на старту такмичења у КЕШ Звезду у 1/16 финала зауставила Ујпешт Дожа. Већ наредне године (1961/62) наша екипа је у Купу сајамских градова преко Базела, Хиберниана и Еспањола стигла до двомеча са шпанским великаном. У полуфиналу је Барселона, коју су предводили Шандор Кочиш и Хосе Антонио Салдуа, била прејака за наш тим, победила је и у Београду (2:0) и на свом терену (4:1).
Освета каталонском клубу уследиће осам месеци касније, у другој рунди истог такмичења. Пре тога Звезда је елиминисала бечки Рапид, а у београдском дуелу је за осам минута од 0:2 преокренула на 3:2. На стадиону Камп Ноу, 19. децембра 1962, голова није било до 86. минута, када је Луис Кубиља погодио Звездину мрежу. Тада гол у гостима није значио ништа, па је за други јануар заказана мајсторица у Ници. Азурна обала била је срећна за нашу екипу, а пенал Боре Костића био је довољан за победу. У четвртфиналу Звезда је играла са Ромом, а после 0:3 на Олимпику, два гола Малешева нису била довољна.
Током 1964. и 1965. црвено-бели су се такмичили прво у Купу европских шампиона, где их је у 1/16 финала зауставио Глазгов Ренџерс, док су се у сезони 1965/66 у првом колу Купа сајамских градова састали са Фиорентином, која је изашла као победник из поменутог двомеча.
Црвена звезда је у богатој историји учествовала у многим светским и европским такмичењима и освојила прегршт важних трофеја, а у њих се убраја и пехар Митропа купа до којег је Црвена звезда стигла 1958. године. Дунавски куп 1958. године је било незванично издање клупског фудбалског такмичења Митропа купа. Такмичење је трајало од 24. маја до 12. јула 1958. године, а учествовале су екипе из Чехословачке, Мађарске, Југославије и Румуније. У осмини финала овог такмичења Црвена звезда се састала у двомечу са чехословачким представником екипом Дукла Пардубице. Звезда је прошла у следећу фазу укупним резултатом 2:0, а тај скор су наши тадашњи првотимци понели из Београда головима Боре Костића и Ранка Борозана што је на крају било довољно за пласман у наредну рунду где смо се састали са Локомотивом из Софије. На првом мечу у Бугарској блистао је Бора Костић са четири поготка, а крајњи резултат гласио је 4:4, да би исти фудбалер био стрелац за наш тим у Београду, а управо тим поготком су се црвено-бели пласирали у наредну рунду.
У полуфиналу Звезда се састала са београдским Радничким, а резултат на стадиону „Земун“ пред четири хиљаде гледалаца гласио је 2:1 у корист нашег тима. Стипић је био двоструки стрелац у 17. и 58. минуту меча, док у реванш утакмици није било голова. Занимљивост овог тунира јесте да су се у финалу играла два меча, тако да је наш тим прво као домаћин дочекао Руду Хвјезду из Брна и убедљиво славио пред 22 хиљаде гледалаца са 4:1. Бора Костић се два пута уписао у стрелце на том дуелу, а поред њега су погађали још Милошевић и Милановић. На реваншу у Брну поново је наш тим однео победу, овога пута са 3:2 головима Костића, Шекуларца и Милановића. Тиме су црвено-бели славили укупним резултатом 7:3 и у витрине по први пут донели пехар Дунавског купа.
Део Црвене звезде су током друге деценије биле истинске легенде као што су Владимир Беара, Рајко Митић, Миљан Миљанић, Владица Поповић, Бранко Станковић, Лазар Тасић, Иван Топлак, Владимир Дурковић, Живорад Јевтић, Војислав Мелић, тренер Миша Павић, голгетер Бора Костић, стрелац првог гола на Маракани – Душан Маравић, али историју нашег клуба су посебним, златним словима исписали друга Звездина звезда – Драгослав Шекуларац и трећа Звездина звезда – Драган Џајић. Нико пре и после Шекуларца није поседовао тако велику страст за лоптом. По таленту и оданости фудбалу, популарни Шеки је једноставно био предодређен да досегне високу класу и постане ас светског формата. Био је човек који је фудбал претварао у уметност, а међу навијачима познат као краљ дриблинга.
Витак, дугог корака, елегантан у сваком покрету, несхватљиво хитар са филигранском техником дриблинга и ударца, Џајић је, иако изразито левоног, био је комплетан играч највећег светског кова. Знао је мајсторски да се у пуном трку пред противником зањише, да га ухвати беспомоћног на “кривој нози” и да појури према голу. У тим моментима погодак или асистенција су били готово неминовни. Џаја је био један од најцењенијих фудбалера 20. века, одиграо је много спектакуларних мечева, постигао сијасет феноменалних и пресудних погодака, многе из слободних удараца. Сасвим је заслужено изабран за најбољег играча Србије и Југославије у прошлом веку. УЕФА је за прославу 50 година постојања бирала идеални тим 20. века и у конкуренцији 50 фудбалера био је и Џајa.
