The bikers gathered Saturday morning in a Moscow suburb to launch the ride to Berlin, planned to retrace the 6,000-kilometre (3,730-mile) march of Soviet troops through Belarus, Poland, the Czech Republic, Slovakia and Austria.
The Night Wolves' long-haired, heavily tattooed leader Alexander Zaldostanov led a column of bikers waving red flags with portraits of Stalin and the wartime slogan "For the Motherland! For Stalin!" out of the gang's clubhouse in northwestern Moscow.
Organizers said around 30 bikers aimed to travel the entire route to Berlin, but it was unclear whether they would be allowed to pass through after both Warsaw and Berlin moved to ban the riders.
A German government source told AFP on Saturday that "entry has been refused to certain leaders of the Night Wolves and visas obtained on false pretences have been annulled."
Polish Prime Minister Ewa Kopacz described the rally as a "provocation" and Warsaw on Friday refused entry to any organized biker group that includes members of the Night Wolves," giving its reason organizational concerns.
Russia's foreign ministry said it was "indignant about the refusal of Polish authorities" and accused Warsaw of lying about the real reasons it was barring the bikers.
The Night Wolves are closely linked to President Vladimir Putin, who has joined the bikers several times at rallies, riding a Harley-Davidson trike, and called them his "friends."
The bikers said they were not discouraged by the bans.
Zaldostanov, 52, nicknamed "the Surgeon" due to his former profession, told journalists on Saturday: "We won't change our plans or our route."
"If they don't let us all come in together, then we will enter one by one, using numerous different entry points," he added.
"If we give up on this rally, then we would have to give up on everything else: May 9th (Victory Day holiday in Russia)... our history and all our values," he said.
But many of the bikers said they had been unable to get visas for Europe's Schengen zone.
Zaldostanov said his passport is still at an embassy in Moscow, not specifying which one, and that he did not yet know if he would get the necessary visa for the trip.
The bikers intend to visit war graves and war memorials in the countries they pass through. They also plan to stop at the former Auschwitz Birkenau death camp, built by the Nazis in occupied Poland and liberated by Soviet forces.
"I don't know what they're afraid of. We are not harming anyone, we are just honouring the memory of those who fell to destroy Fascism," said Alexei Magister, the president of a biker club linked to the Night Wolves.
"We're not afraid of the welcome we'll get in Berlin. Our grandfathers weren't afraid!" said Alexei Vereshchyagin, a biker who was taking a break from fighting Ukrainian forces in the pro-Russian separatist hub of Lugansk.
Members of the Night Wolves rode down en masse to Ukraine's Crimea peninsula just after it was annexed by Russia in March 2014 and members have also fought with pro-Russian separatists in eastern Ukraine.
The Night Wolves biker group started up in 1989 just before the fall of the USSR and has around 5,000 members across the former Soviet Union.
On Saturday, another group of some 200 Russian bikers took part in a memorial ceremony for fallen Soviet soldiers at Braniewo in northern Poland, close to the border with Russia's westernmost Kaliningrad region.
Those Russian bikers were escorted by Polish police from the border.
Russia's ambassador to Poland, Sergei Andreyev, and the governor of the Kaliningrad region, Nikolai Tsukanov, also attended the ceremony.