15 декабря 1939 г. на основе перечисленных рот был организован строительный учебный батальон особого назначения № 800. Немецкая рота в Сляке стала 1-й ротой батальона, рота, расположенная в Бранденбурге, — 2-й, а рота в Мюнстерэйфеле — 3-й ротой батальона. Был также образован организационный штаб во главе с майором Кевишем и штабная рота. Впервые началось формирование подразделений по территориальному и языковому принципу. В 1-й роте преобладали этнические немцы из Судет, Словакии и Польши; во 2-й служили немцы — добровольцы из немецких частей и этнические немцы Румынии, Прибалтики и Палестины; в 3-й роте этнические немцы из Судет и Румынии. 22 февраля 1940 г. в составе батальона была сформирована 4-я рота, основу которой составили судетские и румынские немцы. Позже были организованы взводы из голландских, эльзасских, датских, югославских, швейцарских, латиноамериканских и даже восточноазиатских немцев{164}.
Накануне Западной кампании Абвером была начата работа по привлечению в ряды батальона иностранных добровольцев. Первыми в рядах батальона появились голландцы. От 100 до 200 голландцев были завербованы в батальон при помощи Национал-социалистического союза голландцев в Германии (National-Socialistische Bond van Nederlanders in Duitsland) и его лидера Юлиуса Гердтманна{165}. Подготовка голландцев велась в четырех учебных лагерях, находившихся между Рейном и голландской границей.
10 мая 1940 г. немецкая армия перешла в решительное наступление на Западном фронте. В рамках вторжения в Голландию батальон особого назначения провел ряд диверсионных операций. Наиболее успешной была операция «Геннеп» — захват важного 150-метрового моста через Маас. Эта задача была выполнена 2-й ротой батальона под командованием обер-лейтенанта Вальтера, накануне операции в состав роты были влиты несколько десятков голландцев Гердтманна{166}. Часть диверсантов переоделась в голландскую военную форму, а часть осталась в немецкой и изображала из себя немецких военнопленных. Колонна диверсантов сумела обмануть бдительность голландцев и захватила столь нужный немцам мост.
Таким образом, использование иностранцев в рядах диверсионных частей себя оправдало полностью, а применение диверсионных частей для захвата и сохранения наиболее важных объектов в рамках молниеносной войны доказало свою целесообразность. С этого момента численность диверсионных частей Абвера продолжала неуклонно расти. 15 мая 1940 г. диверсионный батальон Абвера был развернут в 800-й учебный полк особого назначения «Бранденбург». В рядах полка были созданы штаб, связное подразделение и три батальона. Штабные учреждения полка разместились в Берлине, 1-й батальон — в Бранденбурге, 2-й — в Бадене — Унтервальсдорфе (на оккупированной территории Австрии), 3-й — в Ахене. Позже были организованы учебная рота, рота переводчиков и рота агентов (V-leute — Vertrauensleute).
Накануне войны с СССР Абвер усилил работу по вербовке русских белоэмигрантов и представителей национальных диаспор народов Советского Союза. Были организованы украинский батальон «Нахтигаль» («Соловей»), грузинская группа «Тамара» и эстонская группа «Эрна» (более подробно об этих частях смотри соответствующие главы). В апреле 1941 г. 2-й батальон полка принял участие в нападении на Югославию. В ходе боев особо отличились югославские фольксдойче. Тем временем численность полка росла вместе с увеличением числа рот в нем. Накануне вторжения в СССР диверсионные части были распределены по немецким армиям следующим образом: 1-й батальон полка и батальон «Нахтигаль» были переданы в подчинение группы армий «Юг», 2-й — в группу армий «Север», 3-й батальон — в группу армий «Центр». Пополнение из граждан СССР позволило немцам развернуть роту агентов в целый батальон.
Дерзкие и успешные действия немецких диверсантов и их иностранных товарищей повлекли за собой дальнейшее увеличение штатов «Бранденбурга». 20 ноября 1942 г. на основе полка было организовано особое соединение «Бранденбург». В его составе было организовано 5 отдельных соединений. Соединение 801 было сформировано в Бранденбурге на базе 1-го батальона 800-го полка, соединение 802 было образовано в Адмон-те (Штирия) на основе 2-го батальона 800-го полка, соединение 803 было организовано в Дюрене на основе кадра 3-го батальона полка, соединение 804 было сформировано в Лангехаргене на основе 1-й и 2-й рот агентов 800-го полка, роты были пополнены восточными добровольцами и переформированы в два легионерских батальона (Legionärs Abteilungen), 3-й батальон соединения был образован на основе тропической роты лейтенанта фон Кенена, родившегося и выросшего в Юго-Западной Африке{167}. Соединение 805 было образовано в Бранденбурге на основе 3-й, 4-й, 5-й и 6-й рот агентов и 14-й призывной роты 800-го полка.