С началом советско-германской войны в работе РСХА произошли некоторые изменения. У Гейдриха возникла идея провести через «практическую» работу в айнзатцгруппах на Востоке руководителей своих служб, особенно «интеллектуалов». То есть заставить их позаниматься расстрелами коммунистов, противников режима, евреев, цыган. Так, командиром айнзатцгруппы «А», в чью зону входили Прибалтика и Белоруссия, он определил начальника австрийского отделения РСХА Шталекера. А начальника III управления РСХА, человека с двумя высшими образованиями, доктора права и доктора экономических наук Отто Олендорфа Гейдрих сосватал на должность командира айнзатцгруппы D, предназначенной для действий в Южной Украине. Хотел пристроить на аналогичный пост еще одного интеллектуала, Шелленберга, но того не отпустил Гиммлер.

Олендорф, отправившись на Восток, свой пост в РСХА сохранил — командование айнзатцгруппой считалось лишь временной командировкой. Но, конечно, наполняя трупами украинские рвы, он не имел возможности одновременно руководить внутренней контрразведкой СД. И его управление уже почти официально было переподчинено Мюллеру. О том, чтобы откомандировать на фронт шефа гестапо, речи не возникало. Кому-то надо было руководить наведением порядка в тылах и оккупированных странах. А Мюллер в данном качестве уже зарекомендовал себя незаменимым специалистом.

К тому же изменилось служебное положение самого Гейдриха. Борман не забыл содействия, которое оказало ему РСХА после перелета Гесса. Прежде натянутые отношения между ним и Гейдрихом значительно потеплели. И при содействии могущественного руководителя партийной канцелярии шеф РСХА набирал все больший вес. В перспективе он был готов даже перейти дорожку Гиммлеру и начинал поглядывать на кресло министра внутренних дел (на которое давно претендовал рейхсфюрер СС). Но этот пост был еще прочно занят Фриком. Зато освободился другой.

Гитлер был крайне недоволен относительной мягкостью протектора Богемии и Моравии Нейрата, который, по его мнению, либеральничал с чехами, редко применял репрессивные меры. И с подачи Бормана фюрер принял решение назначить к нему более энергичного вице-протектора. На эту роль, при поддержке того же Бормана, выдвинулся Гейдрих. С тем, чтобы остаться одновременно и руководителем РСХА. Гиммлеру подобное назначение очень не понравилось. Он понял, что общий «вес» Гейдриха в нацистской иерархии резко увеличивается. Но против Бормана рейхсфюрер идти не мог. Тот уже успел за несколько месяцев, используя свои таланты, стать «правой рукой» и «тенью» Гитлера, превратиться в незаменимого для него человека.

23 сентября фюрер вызвал Нейрата в Берлин и в очень сильных выражениях обвинил его в «недостатке» твердости, поставив в известность, что назначает ему заместителя. Нейрат не согласился и подал в отставку. Гитлер ее, по своему обыкновению, не принял. Но через несколько дней отправил Нейрата «в отпуск» (в котором он и пробыл потом два года). А Гейдрих стал формально вице-протектором, но реально получил в Чехии полную власть. 29 сентября он перебрался в Прагу, где решил проводить политику «кнута и пряника».

В качестве «пряника» он призвал чехов к сотрудничеству, предлагая те же схемы, которые использовались во Франции. А для поисков контактов с чешской общественностью Гейдрих привез «технического советника», бывшего второго человека в германской компартии Торглера. Что же касается «кнута», то 14 октября Гейдрих доложил Гиммлеру, что намерен поочередно перебрасывать в протекторат все батальоны войск СС, «чтобы производить здесь расстрелы и контролировать казни через повешение». Сообщал, что пока, за две недели, им расстреляно 153 человека и повешено 38. Когда же пражские студенты организовали демонстрацию протеста, новый вице-протектор церемониться не стал, скопом отправил всех участников, 1200 человек, в Заксенхаузен, а 9 активистов повесил.

Руководство спецслужбами Гейдрих не упускал из-под контроля. Был связан с Берлином ежедневной авиапочтой, специальными телефонными и телетайпной линиями и радиосвязью через особую сеть РСХА, вызывал кого нужно к себе или прилетал на совещания сам — в его распоряжении были два самолета, постоянно готовые к вылету. Но с переездом шефа в Прагу ответственности у начальников управлений РСХА прибавилось. Они теперь получили право докладов непосредственно Гиммлеру. Особенно это способствовало возвышению Шелленберга, который стал «любимчиком» рейхсфюрера.

У Мюллера работы тоже хватало. Он был вдобавок к прошлым обязанностям назначен «уполномоченным по вопросам восточноевропейских стран». Был повышен и в звании (возможно, Борман поспособствовал, не забыл оказанную услугу). 9 ноября 1941 г. Мюллер стал генерал-лейтенантом полиции и группенфюрером СС. Но и забот у него прибавилось, круг деятельности возрос. Он руководил созданием сети отделений гестапо на оккупированных советских территориях и ее деятельностью, отдавал приказы об «охранных» или «превентивных» арестах в самой Германии и подконтрольных ей странах.