During the Soviet operation Bagration, Tolsdorff took over command of a scratch force of alert and leave companies, Grenadier-Regiment 1067. He was first ordered to break through to the garrison at Vilnius, which he succeeded in doing (on the way rescuing a German field hospital with 3,000 wounded men). He then took part in the city's defense, later breaking out with other units when a narrow corridor had been created by German relief forces. He and his men had distinguished themselves during the time they defended the city, so much so that Tolsdorff was christened "The Lion of Vilnius" by German propaganda. For his actions here he received the Swords to his Knight's Cross.
Awarded for the excellent leadership of his division during the battle of the Bulge (where it successfully seized and held a river crossing), and later during the retreat through the Eifel region.