In a moment of huge symbolism, soldiers from Britain, France, Poland and the United States paraded on the Moscow square's famous cobbles along with nuclear-capable missiles that once would have been aimed at Western states.
Britain and the United States were the key allies of the Soviet Union in World War II but became bitter postwar foes. France and Poland were occupied by the Nazis but their exiled troops played a major role in the Allied effort.
"Sixty-five years ago, Nazism was defeated and a machine that was exterminating whole peoples was halted," President Dmitry Medvedev said in a speech at the parade. "There was one choice -- either victory or to become slaves."
Two dozen world leaders attended the parade for the 65th anniversary of the victory, including Chinese President Hu Jintao, German Chancellor Angela Merkel and the heads of state of almost all the ex-Soviet nations.
Under blazing sunshine and to the sound of thunderous military music, Britain's 1st Battalion Welsh Guards marched in their full ceremonial uniform including traditional bearskin hats, red jackets and black trousers.
France was represented by the Normandie-Niemen squadron, which fought on the Eastern Front, the United States by a detachment from the 2nd Battalion, 18th Regiment, and Poland by a ceremonial guard of honour.
The presence of the Western troops "shows clearly our solidarity and that general human values are more and more important for the development of the modern world," Medvedev added.
Hundreds of Russian tanks and missile systems rolled through the square past the VIP grandstand erected in front of Lenin's mausoleum, on which Joseph Stalin stood to welcome Soviet troops home in 1945.
Regiments also marched from almost all the ex-Soviet states, with the detachment from Turkmenistan led by a commander on a white stallion, a direct descendant of the steed ridden by Marshal Georgy Zhukov in the 1945 parade.
The parade culminated with the entrance of three nuclear-capable Topol-M missiles, which have a range of 11,000 kilometres (7,000 miles). A procession of 127 military aircraft roared through the sky, some leaving blue, red and white plumes of smoke in the colours of the Russian flag and others flying in formation to spell out the number 65.
Other planes included a special Ilyushin Il-80 designed to accommodate the Russian leadership in case of a nuclear attack. Over 10,000 Russian troops took part in the finely choreographed parade which appeared aimed at impressing the world with Russia's post-Soviet resurgence.
"Greetings, comrades! I congratulate you on the 65th anniversary of victory in the Great Patriotic War," declaimed Defence Minister Anatoly Serdyukov, standing up in a black open-top Zil car as he inspected the Russian troops.
"Hurrah!" replied the troops in chorus, sending a huge wave of sound across Red Square. A civilian and former furniture executive, Serdyukov wore a suit rather than military uniform.
However the parade was also overshadowed by tragedy, with more than 80 coal miners and rescue workers still trapped underground after explosions at a mine in Siberia overnight that killed 12.
With Russia still finding its national identity almost two decades after the collapse of the Soviet Union, the surrender of Nazi forces is seen by the authorities as a moment that can unify modern Russia.
However liberal analysts have expressed cynicism over the Moscow parade costing 1.3 billion rubles (40 million dollars), saying the authorities are using the event for a show of might to reinforce their own power.
The Western allies mark Victory in Europe Day each year on May 8, but Russia celebrates Victory Day on May 9 as the German surrender went into force at 11:01 pm Berlin time, when it was already May 9 in Moscow.
COMMENTS
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ