Первым из созданных в составе вермахта на Восточном фронте мусульманских формирований стал Туркестанский полк (Turkestanisches Regiment). Он был сформирован в соответствии с приказом генерал-квартирмейстера Генштаба сухопутных войск Е. Вагнера «О создании охранных «сотен» из военнопленных туркестанской и кавказской национальности» от 15 ноября 1941 г. при 444-й охранной дивизии, действовавшей в тыловом районе группы армий «Юг». Полк состоял из четырех пехотных рот под командованием немецких офицеров и фельдфебелей и уже зимой 1941–1942 гг. нес службу по охране тыла на территории между устьем Днепра и Перекопом. По документам вермахта Туркестанский полк проходил как 811-й пехотный батальон. Со временем при 444-й дивизии предполагалось создать еще несколько таких батальонов.
Однако из-за решения ОКХ централизовать и упорядочить создание и использование частей восточных легионов этот процесс был изъят из компетенции командования 444-й дивизии. Такое решение было связано с планами немецкого военно-политического руководства по проникновению на Кавказ и так называемым кавказским экспериментом.
На основе этих планов 30 декабря 1941 г. ОКХ приступило к формированию нескольких восточных легионов, которые и были созданы в течение первой половины 1942 г. перед вторжением немцев на Кавказ.
Восточные легионы должны были представлять собой одновременно и запасные части, и центры по подготовке личного состава для боевых частей. Поэтому местом их дислокации и базой был выбран глубокий тыл немецкой армии — Польша, где в январе — феврале 1942 г. было первоначально сформировано 4 легиона. Так, 13 января 1942 г., согласно приказу начальника вооружений сухопутных войск и главнокомандующего армией резерва, были созданы Туркестанский легион (центр формирования на станции Легионово) и Кавказско-магометанский легион (центр формирования на станции Едлин).
А уже 8 февраля последовал приказ о формировании Грузинского легиона (центр формирования в Крушне) и Армянского легиона (центр формирования в Пулавах).
Первоначально Туркестанский легион объединял в своих рядах узбеков, казахов, киргизов, туркмен, каракалпаков и таджиков. Кавказско-магометанский легион — азербайджанцев, дагестанцев, ингушей и чеченцев. Грузинский легион, кроме грузин, включал осетин, абхазов, адыгейцев, черкесов, кабардинцев, балкарцев и карачаевцев. Лишь Армянский легион имел однородный национальный состав.
Чтобы сделать легионы более мононациональными по составу, 2 августа 1942 г. Кавказско-магометанский легион был переименован в Азербайджанский, а из его состава, как и из состава Грузинского легиона, были выведены представители горских народов, объединенные в Северокавказский легион (центр формирования в Весоле). Кроме того, 15 августа 1942 г. в Едлине был организован Волжско-татарский легион, объединивший в своих рядах поволжских татар, башкир, марийцев, мордву, чувашей и удмуртов.
Хотя Грузинский и Армянский легионы перестали, таким образом, быть чисто мусульманскими, в немецких нормативных документах они продолжали учитываться в качестве восточных легионов.
Общее руководство формированием и обучением национальных легионов осуществлял Штаб подготовки восточных легионов (Aufstellungsstab der Ostlegionen), который 23 января 1943 г. был переименован в Штаб командования восточными легионами (Kommando der Ostlegionen). Зимой — весной 1942 г. этот штаб располагался в Рембертове, а летом был переведен в Радом. Командующим восточными легионами в Польше был назначен полковник Р. фон Гейгендорф. Первоначально он обладал правами полкового, а с 1943 г. дивизионного командира.
В своих действиях по организации и подготовке восточных легионов полковник Гейгендорф руководствовался Директивой для формирования восточных легионов, которую 24 апреля 1942 г. издал начальник общего управления командования армии резерва генерал-от-инфантерии Ф. Ольбрихт.
Основным контингентом для пополнения восточных легионов, по крайней мере до того момента, пока немецкие войска не вступят на Кавказ и в Среднюю Азию, должны были быть советские военнопленные соответствующих национальностей. В основном их отбором и сортировкой занимались специально созданные немецкие инстанции. Так, еще весной 1942 г. был сформирован Организационный штаб «К» (»Кавказ»), который развернул активную деятельность по вербовке добровольцев среди военнопленных — уроженцев Кавказа и Средней Азии. В его задачи входило создание комиссий по «фильтрации лагерей военнопленных» и «отделение лиц кавказской национальности от русских для последующей… вербовки».[32]
Прибывшее из лагерей военнопленных пополнение распределяли по подготовительным лагерям, которые имелись у каждого легиона. Так, в Беньяминово располагался подготовительный лагерь Туркестанского и Северокавказского, в Малькинии — Азербайджанского, в Бяла Подляске Грузинского, в Заежирже — Армянского, а в Седлице — Волжско-татарского легионов.