История монумента в Трептов-парке обросла множеством легенд и напрямую связана со Сталиным. После решения возвести «Памятник воинам Советской Армии, павшим в боях с фашизмом» был объявлен конкурс. Его победителем стал Евгений Викторович Вучетич — не только выдающийся скульптор-монументалист, но и солдат Великой Отечественной. Он ушел добровольцем на фронт рядовым в первые дни войны, а к концу 1942 года уже имел звание капитана. При штурме города Любань Ленинградской области получил тяжелую контузию. После войны он станет автором знаменитых памятников «Родина-мать зовет» в Сталинграде, «Родина-мать» в Киеве и многих других…
Вучетич вспоминал, что сразу после Потсдамской конференции его пригласил к себе К. Е. Ворошилов, который посоветовал сделать центральной фигурой монумента Сталина. Скульптор поступил мудрее и сделал два эскиза. На одном — Сталин. На втором — воин-победитель со спасенной немецкой девочкой на руках.
В бронзе была отражена реальная история, произошедшая 26 апреля 1945 года. Двадцатидвухлетний сержант Николай Иванович Масалов, знаменщик 220-го гвардейского стрелкового полка 79-й гвардейской стрелковой дивизии, спас из-под шквального огня ребенка. Сам он позже так описывал эти события: «Под мостом я увидел трехлетнюю девочку, сидевшую возле убитой матери. У малышки были светлые, чуть курчавившиеся у лба волосы. Она все теребила мать за поясок и звала: „Муттер, муттер!“ Раздумывать тут некогда. Я девочку в охапку — и обратно. А она как заголосит! Я ее на ходу и так, и эдак уговариваю: помолчи, мол, а то откроешь меня. Тут и впрямь фашисты начали палить. Спасибо нашим — выручили, открыли огонь со всех стволов». Сержант был ранен в ногу, но девочку донес до своих.
Донёс — рискуя жизнью и прикрывая ребенка своим телом.

Знавший войну не понаслышке, скульптор Вучетич глубоко осознавал величие подвига Николая Масалова. Аналогов ему не было ни в американской, ни в германской, ни в какой иной армии. И потому-то сделал два эскиза.
На первом — Сталин. На втором — солдат с девчушкой.
Оба эскиза выставили для обзора в одном из залов Московского Кремля. Посмотреть работу скульптора пришло много народа. Все столпились около полутораметровой скульптурной фигуры генералиссимуса и громко высказывали свое одобрение. Обернутую в целлофан фигуру солдата с девочкой будто не замечали.
Появился Сталин. Не торопясь прошел вокруг эскизов, повернувшись к скульптору, спросил:
— Слушайте, Вучетич, вам не надоел этот… с усами? — и показал мундштуком трубки в лицо полутораметровой фигуры.
— Это пока эскиз, — попытался кто-то заступиться за скульптора.
— Автор был контужен на фронте, но не лишен языка, — прервал Сталин и устремил взгляд на фигуру под целлофаном. — А это что?
— Это тоже эскиз, — ответил Вучетич.
— Тоже и… кажется, не то же, — заметил Сталин. — Покажите…

Вучетич снял целлофан с фигуры солдата.
Оглядев эскиз памятника, Сталин улыбнулся и сказал:
— Вот этого солдата мы и поставим в центре Берлина на высоком могильном холме… Пусть этот великан в бронзе, победитель несет на своей груди девочку — светлые надежды народа, освобожденного от фашизма.
Только знаете, Вучетич, автомат в руке солдата надо заменить чем-то другим. Автомат — утилитарный предмет нашего времени, а памятник будет стоять в веках. Дайте ему в руки что-то символичное. Ну, скажем, меч. Увесистый, солидный. Этим мечом солдат разрушил фашистскую свастику. Меч опущен, но горе будет тому, кто вынудит богатыря поднять этот меч…

Так было принято решение… Макет памятника скульптор направил в Ленинград, где изготовили 13-метровую 72-тонную фигуру Воина-освободителя. Открыли «Памятник воинам Советской Армии, павшим в боях с фашизмом» 8 мая 1949 года.