Начало военной карьеры
Окончил среднюю школу, затем работал фермером. 1 октября 1934 года поступил вольноопределяющимся в 1-й пехотный полк. 1 июня 1936 года получил звание лейтенанта, 1 октября 1938 — старшего лейтенанта.
Польская кампания
Командовал ротой в 1-й пехотной дивизии. Награждён Железными крестами обеих степеней. В конце кампании был ранен в плечо.
Восточный фронт
В начале кампании против СССР командовал ротой. Бои в Литве, Латвии и Эстонии, вновь тяжело ранен. Произведён в звание капитана и награждён Рыцарским Крестом 4 декабря 1941 года.
Вернулся на фронт в апреле 1942 года, в боях в районе Ладоги лишился правой ступни. За успехи в боях в районе Волховского котла награждён золотым Немецким крестом. Тогда же получил пулевое ранение в голову. 1 января 1943 года получил звание майора и назначен командиром батальона. 15 сентября 1943 года за успешное отражение прорыва советских войск в районе Ладоги награждён Дубовыми Листьями (№ 302) к Рыцарскому кресту.
В 1944 году 1-я пехотная дивизия была передислоцирована на южный участок Восточного фронта, в район Одессы. Там Тольсдорф принял командование полком после гибели командира. Затем он получил ранение в живот, был эвакуирован в тыловой госпиталь, где получил звание подполковника.
После выздоровления направлен в район Вильнюса, где организовал эвакуацию нескольких тысяч раненых до подхода немецких сил под командованием графа Гиацинта Штрахвитца. За эти действия 18 июля 1944 года награждён Мечами (№ 80) к Рыцарскому кресту с Дубовыми Листьями и произведён в полковники. В августе 1944 года Гитлер лично приказал отозвать Тольсдорфа в тыл для формирования 340-й народно-гренадёрской дивизии.
Западный фронт
В ноябре 1944 года сформированная 340-я народно-гренадёрская дивизия была дислоцирована в районе Ахена для защиты подступов к Рейну. 30 января 1945 года Тольсдорф получил звание генерал-майора, 18 марта 1945 — награждён Бриллиантами (№ 25) к Рыцарскому кресту с Дубовыми Листьями и Мечами, произведён в генерал-лейтенанты и назначен командующим 82-м корпусом в Баварии. Тольсдорф стал таким образом самым молодым генерал-лейтенантом в Германии.
8 мая 1945 года, после капитуляции Германии, сдался в плен американским войскам.
После войны
Тольсдорф был отпущен из американского плена 9 мая 1947 года. После плена работал водителем грузовика, рабочим-строителем.
В декабре 1952 года был арестован германскими властями и обвинён в казни капитана вермахта в мае 1945 года. Был приговорён к двум с половиной годам заключения, однако федеральный суд отменил приговор и в итоге признал Тольсдорфа невиновным.
