Орден был учрежден указом Президиума Верховного Совета СССР 8 ноября 1943 года, то есть вскоре после того, как произошли события, справедливо названные советской историографией «коренным переломом в ходе Великой Отечественной войны». По статуту ордена им награждался «высший командный состав Красной Армии за успешное проведение боевых операций в масштабе одного или нескольких фронтов, в результате которых фронтовая обстановка менялась в пользу Красной Армии».

Основа ордена – звезда и расходящиеся лучи, выполненные из платины. «Победа» – самый красивый и большой по размерам советский орден. Расстояние между противолежащими лучами звезды – 72 мм. В лучи звезды вставлены крупные рубины, обрамленные бриллиантами. В расходящиеся лучи также вставлены бриллианты; всего орден служит «оправой» 170 бриллиантам общей массой 16 карат. В центре звезды – голубой эмалевый круг с золотыми изображениями Спасской башни Кремля, здания Сената за Кремлевской стеной и Мавзолея Ленина, а также двух ветвей – лавровой и дубовой. В звезду Спасской башни вставлен рубин, между листьями ветвей – мелкие бриллианты. В нижней части эмалевого круга расположена красная эмалевая лента с надписью «ПОБЕДА», в верхней части круга – надпись «СССР»; обе надписи выполнены белыми эмалевыми буквами.

Орденский знак крепили к мундиру с помощью штифта и носили на левой, а не на правой стороне груди, как все прочие ордена со штифтовым креплением (например, ордена Красной Звезды, Отечественной войны, Суворова, Кутузова, Александра Невского). Следующее исключение из правил состояло в том, что орден размещался ниже всех орденов и медалей (высшие по рангу ордена носят выше всех остальных). Зато планку с лентой ордена «Победа» носили выше всех остальных наград, и она имела ширину 46 мм, а не 24 мм, как прочие орденские планки.

30 марта 1945 года: командующий 2-м Белорусским фронтом Маршал Советского Союза Рокоссовский и командующий 1-м Украинским фронтом Маршал Советского Союза Конев были удостоены орденов «Победа» за освобождение Польши и форсирование реки Одер.

26 апреля: командующий 2-м Украинским фронтом Маршал Советского Союза Малиновский и командующий 3-м Украинским фронтом Маршал Советского Союза Толбухин – за освобождение Венгрии и Австрии.

31 мая: командующий Ленинградским фронтом Маршал Советского Союза Говоров – за освобождение Эстонии. Тем же указом вторым орденом «Победа» награждались командующий 1-м Белорусским фронтом Маршал Советского Союза Жуков – за взятие Берлина и командующий 3-м Белорусским фронтом Маршал Советского Союза Василевский – за взятие Кёнигсберга и освобождение Восточной Пруссии (ныне Калининградская область Российской Федерации).

4 июня: за «планирование боевых операций и координацию действий фронтов в период Великой Отечественной войны» орденом «Победа» были награждены два штабиста. Начальник Генерального штаба генерал армии Антонов стал единственным кавалером ордена «Победа», не имевшим маршальского звания. Представитель же Ставки Верховного главнокомандующего Маршал Советского Союза Тимошенко был удостоен награды исключительно за то, что в канун войны занимал пост наркома обороны СССР; в его лице высшим военным орденом была отмечена немногочисленная группа военачальников, прославившихся еще в Гражданскую войну.

26 июня, через два дня после того, как на Красной площади прошел Парад Победы, заслуги Верховного главнокомандующего Сталина были отмечены Президиумом Верховного Совета СССР, который специальным указом присвоил ему звание Героя Советского Союза и наградил вторым орденом «Победа». На следующий день, 27 июня, был подписан указ об учреждении воинского звания Генералиссимуса Советского Союза и о присвоении этого звания Сталину.

3 сентября: командующий Дальневосточным фронтом Маршал Советского Союза Мерецков награжден орденом «Победа» за разгром японской императорской Квантунской армии и победу над Японией.

Таким образом, кавалерами ордена «Победа» стали 11 человек: генералиссимус Сталин (дважды), 9 маршалов (Жуков и Василевский – дважды) и генерал армии Антонов. Однако этим список награжденных не исчерпывается.

В июне 1945 года все советские маршалы и многие генералы получили ордена стран – союзников СССР по антигитлеровской коалиции. Например, маршал Жуков стал кавалером британского ордена Бани I степени, французского Военного креста, американского ордена Почета степени главнокомандующего, итальянской партизанской медали Гарибальди, польских орденов Virtuti Militari I степени и Polonia Restituta II степени, югославского ордена «Свобода», чехословацких Военного креста и ордена Белого льва I степени, командором французского Почетного легиона. Сталин решил сделать ответный жест и наградить орденом «Победа» военачальников союзных армий, благо награда идеально для этого подходила. По мнению главковерха Сталина, можно и должно было дать звание Героя Советского Союза летчику авиаполка «Нормандия-Неман» капитану маркизу Ролану де ля Пуапу, однако украсить Золотой Звездой и орденом Ленина френч британского фельдмаршала графа Монтгомери ему возможным не представлялось. Сталин решил, что ордена Ленина, Отечественной войны и Красного Знамени могут быть вручены только тем иностранцам, которые принимали непосредственное участие в сражениях в составе подразделений, входивших в Красную (а затем Советскую) армию; командующие же союзными армиями должны быть отмечены по-иному. В итоге состоялось еще пять награждений орденом «Победа».

Верховный главнокомандующий союзными экспедиционными вооруженными силами в Западной Европе генерал армии США Дуайт Дэвид Эйзенхауэр. Самый известный американский военачальник был отмечен за подготовку и осуществление операции «Оверлорд» (высадка союзников в Нормандии), освобождение Франции, Бельгии, Нидерландов и успешное наступление в Западной Германии. Эйзенхауэр был и остается единственным президентом США (1952–1960), имевшим советскую награду.

Командующий группой союзных армий в Западной Европе фельдмаршал Великобритании сэр Бернард Лоу Монтгомери, граф Аламейнский. Ему вменялось в заслугу то же самое, что и Эйзенхауэру, но при этом Советское правительство оценило еще и победу, которую Монтгомери одержал в 1942 году под Эль-Аламейном, где был разбит Африканский корпус под командованием любимца Гитлера генерал-фельдмаршала Эрвина Роммеля.

Верховный главнокомандующий народно-освободительной армией Югославии маршал Иосип Броз Тито. В период с 1940 по 1945 год армия Тито сковывала на Балканах значительные германо-итальянские силы: только рейх был вынужден держать в Югославии три армейских корпуса полного состава. Тито успешно сражался не только с немцами, но и с формированиями усташей (хорватских фашистов) Анте Павелича и четников (сербских монархистов) Дражи Михайловича.

Верховный главнокомандующий Войска Польского на территории СССР маршал Михал Роля-Жимерский. Поскольку у Сталина, Трумэна и Черчилля, готовившихся к Потсдамской конференции, были диаметрально противоположные воззрения на будущее Центральной и Восточной Европы, Сталин решил отметить высшей наградой командующих двух крупнейших союзных армий этого региона – Тито и Роля-Жимерского. У последнего награждения был и политический смысл: СССР не признал легитимными представителями польского народа ни лондонское правительство, ни действовавшие на территории Польши крупные партизанские соединения генерала Бур-Комаровского, ни ушедшую в 1942 году из СССР через Иран на Ближний Восток и в Западную Европу польскую армию генерала Андерса. Союзниками Советского Союза признавались лишь солдаты и офицеры сформированной в Казахстане дивизии имени Тадеуша Костюшко, которая последовательно превратилась в корпус, армию и, наконец, в 300-тысячное Войско Польское, 1-я и 2-я армии которого принимали участие в штурме Берлина.