Za zasługi w dowodzeniu batalionem, we wrześniu 1943 zostaje odznaczony Liśćmi Dębu do Krzyża Rycerskiego, a dwa miesiące później obejmuje dowództwo 22 pułku fizylierów. W czasie walk w okolicach Odessy otrzymał postrzał w brzuch z bliska i przebywał w szpitalu do połowy 1944 roku.
1 kwietnia 1944 został awansowany na podpułkownika, a od 1 czerwca rozpoczął pracę jako wykładowca taktyki w szkole kadetów w Metz. 1 lipca 1944 powraca na front jako dowódca 22 pułku i bierze udział w obronie okrążonego Wilna. Za wybitne osiągnięcia w czasie tych walk został 18 lipca 1944 odznaczony Mieczami do Krzyża Rycerskiego oraz zyskał przydomek „Lew z Wilna”, a 1 sierpnia został awansowany na pułkownika.
W sierpniu 1944 obejmuje dowództwo szkolnej dywizji piechoty, z której później sformowano 340 Dywizję Grenadierów Ludowych. Tolsdorff dowodził tą dywizją na froncie zachodnim m.in. podczas ofensywy w Ardenach. 30 stycznia został mianowany generałem majorem, a za zasługi w trakcie walk odwrotowych nad Renem 18 marca został awansowany na generała porucznika (w owym czasie był najmłodszym oficerem w tym stopniu) oraz udekorowany Brylantami do Krzyża Rycerskiego. W kwietniu 1945 roku objął dowództwo LXXXII Korpusu Armijnego, który walczył w Bawarii. 9 maja 1945 dostał się do niewoli amerykańskiej, z której został zwolniony dwa lata później.