На Нюрнбергском процессе по этому поводу Штольце сказал следующее: «В начале 1938 года получил указание от Канариса о переключении имеющейся агентуры из числа украинских националистов на непосредственную работу против Советского Союза. Через некоторое время на квартире петлюровского генерала Курмановича я осуществил встречу с Коновальцем, которому передал указание Канариса… Коновалец согласился… Об этом Коновалец информировал письменно главу униатской церкви митрополита Шептицкого: «Обращаю внимание Вашей экселенции на то, с какой последовательностью претворяются планы великого фюрера».
История возникновения подразделения «Бранденбург-800» следующая. Еще задолго до 1 сентября 1939 года на польско-немецкой границе, особенно в районе Силезии, шла так называемая «малая война». Через границу в Польшу проникали немецкие боевые группы «Эббингауз» и более крупные формирования, которые атаковали польские таможенные посты, пограничные заставы, вокзалы, шахты. Группы «Эббингауз» действовали и в тылу польских войск и во время сентябрьской кампании. Родоначальником этих диверсионных групп был капитан фон Хиппель. Совершая жестокие преступления среди безоружного польского населения, они приобрели репутацию убийц. Правда, большинство акций немецких боевиков заканчивалось провалом, и во время боев они потеряли более половины своего состава. Из остатков этих боевых групп, организованных немецкой разведкой в 1938-39-х годах, позже и были созданы подразделения полка специального назначения «Бранденбург».
15 октября 1939 года уцелевшая рота боевиков была доставлена в город Бранденбург и реорганизована в подразделение под кодовым названием «800-я учебная строительная рота для специальных заданий». В январе 1940 года роту преобразовали в батальон. Часть его выделили в 100-й батальон специального назначения, который участвовал в нападении на Голландию и Бельгию. В октябре 1940 года появился полк учебный полк спецназначения «Бранденбург-800», который был подчинен диверсионному отделу Абвера (так называемому «Абверу-2»), под командованием Э.Лахаузена. Штаб полка находился в Берлине. Отдельные батальоны размещались в разных городах Германии и предназначались для операций в определенных районах.
Все батальоны и роты «Бранденбурга» предназначались для совершения диверсий в тылу противника незадолго до наступления регулярных войск . Планировались рейды для захвата стратегических объектов: мостов, туннелей, коммуникационных узлов и т.д. В ходе обучения солдаты осваивали технику разминирования и удержания объектов до подхода передовых частей. Кроме того, они выполняли шпионские и разведывательные задания перед началом операций. Обязательное условие – солдаты должны были быть знакомы с языком предполагаемого противника.
При обучении большое внимание уделялось незаметному передвижению на местности, умению бесшумно убивать, стрельбе из разных видов оружия, марш-броскам, ориентации, выживанию и маскировке. Отношения между командирами и подчиненными в батальонах отличались от обычной военной дисциплины и носили скорее дружеский характер. В акциях применялись всевозможные трюки: диверсанты действовали в гражданской одежде либо переодевались в мундиры противника (в нарушение международного права ). Разрешалось все.
Солдаты «Бранденбурга», переодетые в чужие мундиры, неоднократно изображали из себя раненых или колонны снабжения. Кроме того, они пользовались формой железнодорожников, шахтеров, притворялись почтальонами, сторожами и даже гражданскими беженцами. Ими неоднократно совершались военные преступления .
Переставленные дорожные указатели, поваленные столбы телеграфной и телефонной связи, колодцы с отравленной водой, внезапно вышедшие из строя семафоры и стрелки на железнодорожных путях – все это тоже работа «Бранденбурга». Группы «Бранденбурга» сыграли значительную роль во время кампании на Западе против Норвегии, Дании, Голландии и Бельгии. Они выполнили множество диверсий и актов саботажа, способствуя молниеносным победам немецких войск.
В 1942 году появились две особые роты: 15-я, размещенная в финской части Карелии и «Бергманн» (Горец), состоявшая из чеченцев. К ним вскоре добавились персидская, арабская и индийская роты. Одновременно были расширены немецкие батальоны. В результате в 1942 году полк стал дивизией, но сохранил прежнее название.
Именно в полку спецназначения «Бранденбург-800» в марте 1941 и был сформирован батальон «Нахтигаль», полностью состоявший из бандеровцев (украинских нацистов, принадлежавших к ОУН-б). Немецким командиром батальона был назначен представитель Абвера обер-лейтенант Альбрехт Герцнер, а офицером связи – представитель НСДАП обер-лейтенант Теодор Оберлендер; украинским командиром – капитан Абвера и сотник по совместительству Р.Шухевич, представлявший ОУН-б. Во главе рот и взводов стояли украинские командиры, при которых находились немецкие офицеры связи и инструкторы. Следует отметить, что украинские командиры были в подчинении у немецких, и зачастую выполняли только роль переводчиков. В батальоне имелся и собственный капеллан греко-католического (униатского) вероисповедания – им стал бандеровец Иван Гриньох.
После принятой 18 июня присяги на верность Украйиньський Дэржави (Украинскому Государству) батальон отбыл в действующую армию и с первых дней войны принимал активное участие в боевых действиях, будучи приданным вместе с 1-м батальоном полка спецназначения «Бранденбург-800» 1-й горнострелковой дивизии.
В средине апреля 1941 на территории Австрии было начато формирование батальона «Роланд», также вошедшего в состав полка спецназначения «Бранденбург-800». В отличие от «Нахтигаля», он был укомплектован мельниковцами (украинскими нацистами, принадлежщими к ОУН-м) – эмигрантами первой волны и их потомками. Кроме того, до 15% от общей численности составляли украинские студенты из Вены и Граца. Кроме украинцев в личном составе батальона числились бельгийские, голландские и французские фашисты. Командиром батальона был назначен бывший офицер польской армии майор Е.Побигущий. Все остальные офицеры и даже инструкторы были украинцами, в то время как германское командование представляла группа связи в составе 3 офицеров и 8 унтер-офицеров. Обучение батальона проходило в замке Зауберсдорф недалеко от города Винер-Нойштадт. В первых числах июня 1941 года батальон отбыл в Южную Буковину, где еще около месяца проходил интенсивное обучение, по завершении которого походным маршем вместе с румынскими войсками двинулся в район Ясс, а оттуда через Кишинев и Дубоссары – на Одессу. В конце августа батальон был отведен с фронта для продолжения обучения. Причиной была его малая пригодность для выполнения поставленных задач.
Одновременно с формированием украинских батальонов, в польском городе Закопане создается школа Гестапо, куда гитлеровцы, по согласованию с Бандерой (агент Абвера «Серый»), отбирают 120 «лучших из лучших» бандеровцев во главе с Николаем Лебедем («Максим Рубан») и ускоренным порядком обучают их ремеслу палачей, натаскивая на допросах арестованных евреев и участников польского сопротивления.
Кроме того, бандеровцы создали и передали под командование фашистов украинскую вспомогательную полицию (УВП), которая идеологически и политически была подчинена ОУН-б. Служивших в карательных батальонах местное население прозвало «шуцманами».
30 июня 1941 г. диверсионный батальон «Нахтигаль» под командованием Р.Шухевича и 1-й батальон «Бранденбург» заняли оставленный советскими войсками Львов. «Нахтигалевцев» (бойцов батальона «Нахтигаль») жители Львова назвали «пташныкамы» – из-за знаков (фашистских орлов), которые были на их автомобилях и мотоциклах. «Пташныкы» были в немецкой форме и с немецкими знаками различия, а на рукоятках штыков имели сине-желтые банты.