Уже в подготовительных лагерях будущие легионеры разбивались по ротам, взводам и отделениям, затем приступали к обучению. Как правило, оно заключалось в общефизической и строевой подготовке, а также в усвоении немецких команд и уставов. Строевые занятия проводились командирами рот немцами с помощью переводчиков, а также командирами взводов и отделений из представителей данной национальности, прошедшими двухнедельную подготовку в специальной школе на станции Легионово. Эта школа занималась обучением младшего командного состава и офицеров - лейтенантов и капитанов.
По завершении начального курса обучения легионеры переводились в батальоны в центрах формирования легионов, где переходили к тактической подготовке и изучению материальной части оружия. Предполагалось, что в составе этих батальонов они впоследствии отправятся на фронт.
Каждый батальон должен был иметь в своем составе 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 рядовых.
У батальонов, сформированных на Украине, была и другая номенклатура. Они имели двойную нумерацию, в которой первая римская цифра означала порядковый номер батальона, а вторая, арабская, - номер дивизии, предоставившей кадровый персонал.