Уже в подготовительных лагерях будущие легионеры разбивались по ротам, взводам и отделениям, затем приступали к обучению. Как правило, оно заключалось в общефизической и строевой подготовке, а также в усвоении немецких команд и уставов. Строевые занятия проводились командирами рот немцами с помощью переводчиков, а также командирами взводов и отделений из представителей данной национальности, прошедшими двухнедельную подготовку в специальной школе на станции Легионово. Эта школа занималась обучением младшего командного состава и офицеров — лейтенантов и капитанов.
По завершении начального курса обучения легионеры переводились в батальоны в центрах формирования легионов, где переходили к тактической подготовке и изучению материальной части оружия. Предполагалось, что в составе этих батальонов они впоследствии отправятся на фронт.
Каждый батальон должен был иметь в своем составе 3 стрелковые, пулеметную и штабную роты по 130–200 человек в каждой; в стрелковой роте — 3 стрелковых и пулеметный взводы, в штабной — взводы противотанковый, минометный, саперный и связи. Таким образом, общая численность батальона в среднем составляла от 800 до 1000 солдат и офицеров, в том числе до 60 человек немецкого кадрового персонала: 4 офицера, 1 военный чиновник, 32 унтер-офицера и 23 рядовых. У немецких командиров батальонов и рот были заместители-дублеры из числа представителей данной национальности. Командный состав ниже ротного звена комплектовался исключительно национальными кадрами, прошедшими подготовку в школе в Легионово.
Таким образом, к весне 1942 г. первые батальоны восточных легионов закончили свое обучение и затем были отправлены на Восточный фронт (главным образом на Кавказ и под Сталинград). Это происходило в три этапа.
1. К концу 1942 г. были отправлены: 6 туркестанских (450-й, 452-й, с 781-го по 784-й), 2 азербайджанских (804-й и 805-й), 3 северокавказских (800, 801 и 802-й), 2 грузинских (795-й и 796-й) и 2 армянских (808-й и 809-й) батальона.
2. В начале 1943 г. за ними последовали: 5 туркестанских (с 785-го по 789-й), 4 азербайджанских (806, 807, 817, и 818-й), 1 северокавказский (803-й), 4 грузинских (с 797-го по 799-й и 822-й), 4 армянских (с 810-го по 813-й) и 3 волжско-татарских (825, 826 и 827-й) батальона.
3. Во второй половине 1943 г. были отправлены: 3 туркестанских (790, 791 и 792-й), 2 азербайджанских (819-й и 820-й), 3 северокавказских (835, 836 и 837-й), 2 грузинских (823-й и 824-й), 3 армянских (814, 815 и 816-й) и 4 волжско-татарских (с 828-го по 831-й) батальона.
Всего же до упразднения Штаба командования восточными легионами в Польше в октябре 1943 г. здесь были сформированы 53 полевых батальона: 14 туркестанских, 8 азербайджанских, 7 северокавказских, 8 грузинских, 9 армянских и 7 волжско-татарских, общей численностью около 53 тыс. человек.
Польша не была единственным местом формирования частей восточных легионов. Так, после зимних боев 1941–1942 гг. из состава группы армий «Центр» на Украину была выведена 162-я пехотная дивизия вермахта. Согласно приказу ОКБ ее предстояло преобразовать в еще один учебный центр по подготовке восточных войск, с теми же целями и задачами, что и в Польше.
Новые центры с учебными лагерями были развернуты на территории Полтавской области: в Ромнах — Туркестанский; в Прилуках — Азербайджанский, в Гадяче — Грузинский, в Лохвице — Армянский и в Миргороде Северокавказский легионы.
Создание Волжско-татарского легиона планировалось в будущем, однако он так и не был сформирован.
В Миргороде также находился и штаб формирования легионов, который официально назывался Штаб подготовки и обучения иностранных добровольческих формирований из советских военнопленных (Aufstellungs — und Ausbildungsstab fur ausldndische Freiwilligen — Verbande aus sowjetrussischen kriegsgefangenen). Начальником штаба был назначен полковник (с 6 сентября 1942 г. — генерал-майор) О. Риттер фон Нидермайер, который до лета 1941 г. был уполномоченным офицером абвера при Особом штабе «Ф».
Как и в случае с формированием восточных легионов на территории Польши, все военнопленные, отобранные специальными комиссиями, поступали в подготовительные лагеря. В данном случае они находились в Лубнах и Хороле.
Численность и структура батальонов, сформированных на Украине, практически не отличались от батальонов, сформированных в Польше. Единственным исключением было соотношение немецкого и национального кадрового персонала. Если в Польше немцев было не более 60, то здесь их должно было быть не более 37 человек: 4 офицера,
1 военный чиновник, 7 зондерфюреров, 15 унтер-офицеров и 10 рядовых.
У батальонов, сформированных на Украине, была и другая номенклатура. Они имели двойную нумерацию, в которой первая римская цифра означала порядковый номер батальона, а вторая, арабская, — номер дивизии, предоставившей кадровый персонал.