Отношения Гиммлера с Гейдрихом к тому моменту стали более сложными, хотя Гейдриху, в мае 1940 г. покинувшему свой офис, чтобы летать с Люфтваффе над поверженной Францией, оставалось жить всего два года. Из этих двух лет первые 15 месяцев были потрачены на подготовку айнзацкоманд к войне против России летом 1941 и на усовершенствование системы уничтожения в лагерях, а последние девять месяцев Гейдрих провел, выполняя обязанности протектора рейха в Чехословакии, где и был убит в мае 1942 года. В этот период он явно считал себя фаворитом Гитлера, предназначенным для продвижения на министерский уровень, обойдя Гиммлера в движении к вершине иерархической лестницы. Между тем самый могущественный подчиненный Гиммлера обращался с ним как с союзником, и они в тесном контакте работали вместе над планами захвата России.
13 марта 1941 года Гитлер издал директиву, подписанную Кейтелем, касающуюся предстоящей кампании на востоке. Директива обеспокоила Верховное командование; в ней говорилось, что «в области проведения операций рейхсфюреру СС вверены фюрером задачи подготовки политического управления — задачи, проистекающую из борьбы двух оппозиционных политических систем. В пределах этих задач рейхсфюрер СС может действовать независимо и на свою ответственность». Гитлер, не вполне удовлетворенный тем, что поручил задачу искоренения коммунизма в России Гиммлеру, а Геринга, ответственного за четырехлетний экономический план, снабдил полномочиями на изъятие с оккупированных территорий провизии и других ценных для Германии продуктов, привлек к делу Альфреда Розенберга, старого интеллектуала партии, и назначил его министром будущих оккупированных территорий на Востоке. Это назначение было столь нелепо, что могло быть объяснено лишь как формальная попытка противостоять объединенной и возрастающей власти Гиммлера и Гейдриха или потенциальной жадности агентов Геринга.
В период интенсивных приготовлений ко вторжению в Россию, которые велись параллельно с подготовкой к массовому уничтожению нежелательных людей, Гиммлеру и Гейдриху пришлось разрабатывать планы для айнзацкоманд, которые были бы приемлемы, с одной стороны, для армии, а с другой, по крайней мере номинально, для Альфреда Розенберга. Розенберг постоянно пытался вмешаться в планы, которые готовил Гейдрих, хотя Гиммлер презрительно игнорировал его существование. Эти разногласия очень сблизили Гейдриха и Мартина Бормана, могущественного помощника Гитлера, поскольку Борман неодобрительно относился к Розенбергу, одержимому идеей сыграть роль балтийско-немецкого освободителя русского народа от советской тирании. Что касается армии, то в июне от Шелленберга потребовали использовать легальную дипломатию, чтобы провести переговоры о приемлемых условиях с генералом Вагнером, представляющим верховное командование; задуманный Шелленбергом и в конце концов подписанный Вагнером план освобождал полицию безопасности и СД от контроля армии вне территории непосредственных боевых действий, предоставляя им вести самостоятельную кампанию. Фактически же, ожидалось, что армия будет помогать им в их зверствах.
Когда, после долгой отсрочки, 22 июня 1941 года наконец началось вторжение в Россию, Гейдрих снова исчез, чтобы летать с Люфтваффе, и однажды его самолет сильно повредила русская зенитная артиллерия. Ему удалось посадить самолет у немецкой границы, и, раненый в ногу, он ползком добрался до своих. За этот подвиг он получил от Гитлера Железный крест первой степени, а Гиммлер просто обезумел, узнав, какой опасности он подвергался. Пока Гейдрих летал над советскими территориями, его айнзацкоманды начали свои страшные избиения, расстрелы, повешения и террор в отношении пленных, коммунистов и партизан, а также целых общин евреев и цыган.
После войны Отто Олендорф, один из интеллектуалов, служивший у Гиммлера и возглавлявший айнзацкоманду, сделал заявление под присягой, которое разоблачает ужасные подробности работы этих диверсионно-десантных отрядов.
«В июне 1941 года Гиммлер назначил меня командующим одной из особых групп действия, которые формировались тогда для сопровождения сил немецкой армии в российскую кампанию… Гиммлер утверждал, что важной частью нашей задачи является уничтожение евреев — мужчин, женщин и детей — и коммунистических руководителей. Мне сообщили о нападении на Россию за две недели… Когда немецкая армия вторглась в Россию, я был командиром айнзацкоманды Д в южном секторе… она ликвидировала приблизительно 90 000 человек — мужчин, женщин и детей,, осуществляя эту программу уничтожения… Отобранный отряд… входил в деревню или город и приказывал известным в населенном пункте евреям собрать всех евреев с целью переселения. От них требовали взять с собой ценные вещи… а незадолго до казни сдать верхнюю одежду. Мужчин, женщин и детей приводили к месту казни, в большинстве случаев расположенному вблизи противотанкового рва, выкопанного глубже обычного. Затем их расстреливали, а трупы сбрасывали в ров… Весной 1942 года мы получили от шефа полиции безопасности и СД в Берлине передвижные газовые камеры… Мы получили приказ пользоваться этими фургонами для убийства женщин и детей. Как только отряд набирал достаточное количество жертв, для их ликвидации высылали фургон».
