После нападения Германии на СССР уже 29 июня 1941 г. Прютцман стал также высшим руководителем СС и полиции на Севере России, предполагалось, что свою штаб-квартиру он разместит в Риге, которую еще только предстояло занять. Вообще, Прютцман должен был возглавить карательный аппарат первого административно-территориального образования на оккупированных советских территориях – рейхскомиссариата «Остланд». Главной задачей, поставленной перед Прютцманом, наряду с выявлением и уничтожением евреев была борьба с партизанским движением. Деятельность Прютцмана на оккупированных территориях по всем направлениям развивалась так, как того желал Гиммлер. Во многом этому способствовали националистические и антисоветские настроения местного населения Прибалтики, следствием чего стало фактическое отсутствие здесь массового партизанского движения. Серьезные проблемы возникли лишь на территории Белоруссии, но и здесь Прютцман проявил большую активность. Его успехи были отмечены 9 октября 1941 г. Железным крестом 2-го класса.
Тем временем в другом рейхскомиссариате на оккупированных восточных территориях – Украине – возникли определенные проблемы. Высший руководитель СС и полиции на Юге России обергруппенфюрер СС и генерал полиции Фридрих Еккельн особыми успехами в борьбе с партизанами похвастаться не мог, поскольку основные свои силы бросил на массовое уничтожение евреев. На это не обратили бы внимания, но здесь сказались особенности личности Еккельна. Он был человеком грубым, бесцеремонным и тяжелым и вскоре вступил в конфликт с рейхскомиссаром Эрихом Кохом, который также являлся гаулейтером Восточной Пруссии. Гиммлер, всегда старавшийся поддерживать хорошие отношения с партийной верхушкой, немедленно произвел рокировку, поменяв местами Еккельна и Прютцмана, последний хорошо знал Коха по службе в Восточной Пруссии и их отношения всегда были ровными. Таким образом, Прютцман, которому 9 ноября 1941 г. присвоили звания обергруппенфюрера СС и генерала полиции, оказался во главе карательного аппарата рейхскомиссариата «Украина».
Прютцман развил на Украине чрезвычайную активность, как в области «решения еврейского вопроса», так и на поприще борьбы с партизанами. Его заслуги в последней были отмечены боевыми наградами: медалью «За зимнюю кампанию на Востоке 1941/42» (он получил ее 17 сентября 1942 г.) и Железным крестом 1-го класса (20 января 1943 г.), кроме того он еще получил и Крест военных заслуг 1-й степени с мечами (1 марта 1943 г.). Как уже и упоминалось выше 9 октября 1943 г. Прютцман также стал верховным руководителем СС и полиции на Украине, получив чрезвычайные полномочия. Главной задачей на этом посту стало объединение всех мероприятий по борьбе с партизанами. Здесь мы не будем останавливаться на деятельности Прютцмана на Украине и вообще на Юге России: чтобы описать карательную политику оккупантов в этом огромном регионе понадобится отдельная книга. Лишь упомянем, что за то время, что Прютцман провел на Украине в 1941–1944 гг., здесь было уничтожено около пяти миллионов советских граждан (свыше 3,8 миллиона местных жителей и около 1,5 миллиона военнопленных) и 2,4 миллиона человек вывезено на принудительные работы в Германию – погиб каждый 6-й житель Украинской ССР.
К концу своего срока на Украине Прютцман фактически полностью сосредоточился на борьбе с партизанами. Параллельно весной-летом 1944 г. он возглавил сводную боевую группу «Прютцман» (