9. јуна 1945. Врховни савет СССР-а издао је два указа о новим војним наградама. Први се тицао медаља за заузимање Кенигсберга, Будимпеште, Беча и Берлина. Други за ослобођење Београда, Варшаве и Прага. Тако је одлучено да се обележе заслуге војника који су учествовали у операцијама за заузимање шест европских престоница и другог највећег политичког центра у Немачкој. Од седам наведених градова, Црвена армија је прва ступила управо на улице Београда.
У случају Београда ради се управо о ослобађању, а не о освајању, што потврђује општа реакција локалног становништва и активно учешће локалних антифашистичких снага. Друго, нема сумње да су Титови партизани, чак и уз велике напоре и жртве, могли самостално да ослободе Београд. А у случају Варшаве и Прага то је тешко замислити. И најзад, Немци су главни град Југославије држали не као стратешку линију одбране, већ као важан пункт на путу повлачења група војске Е и Ф, које су у сваком случају одлазиле са Балкана.
Са чисто стратешке тачке гледишта, совјетска команда у ослобођењу Београда видела не само могућност да отежа немачким трупама повлачење из Грчке, Југославије и Албаније, већ и прелиминарну етапу продора у Немачку.
Немци, са друге стране, такође нису намеравали да држе Београд до последњег даха, тако да су губици совјетских трупа били много мањи чак и у поређењу с Прагом и Бечом, а да не спомињемо вишемесечне операције за заузимање Варшаве, Будимпеште и Кенигсберга. Сходно томе, број награђених за београдску операцију такође је био најмањи — око 68 хиљада према 277 хиљада за Беч и 395 хиљада за Праг.
Ватромет у част ослобођења Београда организован је у Москви 20. октобра 1944. године. Око две хиљаде совјетских војника добило је југословенске награде за учешће у ослобађању ове земље, укључујући 16 народних хероја Југославије. 30 војних јединица звале су се „београдске“.
Идеја да се доделе „ослободилачке» медаље припада начелнику Главне команде позадине, генералу Црвене армије Андреју Хрулеву. За награду у част ослобођења Београда припремљено је пет скица, а изабран је заједнички рад уметника Кузњецова и Скоржинске (њихов је тандем победио и у случају медаље за Праг).
Општи изглед медаље „За ослобођење Београда“ је традиционалан за овакве награде. Пречник му је 32 мм, израђен је од месинга. И аверс и реверс имају обод, а слике и натписи су конвексни.
На предњој страни медаље око обода пише „За ослобођење“, у средини — „Београда“. Натпис је крунисан петокраком звездом са ловоровим венцем. На полеђини медаље датум „20. октобар 1944. године“ је украшен звездицом. Данас ова награда код колекционара кошта око 10-10,5 хиљада рубаља (или 150 евра).
Медаљу је могао да добије и маршал и обичан редов. Није познато да ли је Јосип Броз Тито имао такву медаљу, али уручена је и маршалу Толбухину, и начелнику штаба фронта, будућем маршалу Семјону Бирјузову и команданту артиљерије, такође будућем маршалу Митрофану Неделину и команданту 4. гардијског механизованог корпуса Владимиру Жданов, који је директно руководио операцијом.
Потешкоће у вези ове медаље настале су након свађе 1948. године Јосипа Броза и Јосифа Стаљина. Постоје докази да је многим војницима и официрима „препоручено“ да медаљу „За ослобођење Београда“ замене најближој у рангу.
Нико није желео да одустане од награде и скупоцених сећања повезаних са њом. Узгред, након смрти награђеног претпостављало се да се медаља врати у наградни фонд, али одлуком Председништва Врховног Савета 5. фебруара 1951. одлучено је да остане у породици.
Ситуација је била компликованија са официрима, генералима и маршалима који се нису повукли из армије а њихова даља каријера је зависила и од спремности да предају или не предају југословенске и совјетске награде „које су изгубиле вредност“.
Толбухин је умро 1949. Постоје докази да је Жданов био у сукобу са командом јер није желео да се одрекне титуле Народног хероја Југославије, а да не спомињемо „београдску“ медаљу. Вероватно је ту одговор на питање зашто је, након што је 1944. добио чин генерал-потпуковника, генерал-пуковник постао тек након двадесет година.
Неки парадокс се крије у томе да је за медаљу проливено најмање крви у поређењу са заузимањем других европских градова, а фатално је утицала на судбину најпознатијих људи који су њоме награђени.
Главни маршал артиљерије Митрофан Неделин погинуо је 24. октобра 1960. године на полигону Бајконур током експлозије ракете Р-16, а заједно са њим још 77 људи.
А затим се догодила трагедија директно повезана са Београдом.
Деветнаестог октобра 1964. године, приликом слетања, авион ИЛ-18 срушио се на Авалу са совјетском делегацијом која је стигла на прославу 20. годишњице ослобођења града.
Погинуло је 16 чланова посаде, као и чланови делегације: начелник Генералштаба Совјетске војске маршал Бирјузов, начелник Академије механизованих снага генерал-пуковник Жданов, начелник Административног одељења Централног комитета КПСС генерал-мајор Николај Миронов, заменик начелника Војне академије „Фрунзе“ генерал-потпуковник Николај Шкодунович, генерал-потпуковник резерве херој Совјетског Савеза Иван Кравцов, пензионисани генерал-мајор Леонид Бочаров.
Сви су сахрањени у Москви на Новодевичјем гробљу изузев Бирјузова, чији је пепео сахрањен у зидинама Кремља.
У Београду је на месту несреће подигнут споменик у облику два сломљена крила, а крај споменика пише:
„Овде су у авионској несрећи у јутро 19. октобра 1964. године погинули совјетски хероји, наши ратни другови и пријатељи. Октобра 1944. овде су се борили за слободу Београда. Овде октобра 1964. улазе у легенду нашег града. Постају знамен братства и заједничке борбе.“