Według koncepcji głównego ideologa hitlerowskiego Alfreda Rosenberga Legiony Wschodnie miały się składać jedynie z ochotników spośród narodów nierosyjskich ZSRR. Decyzją Adolfa Hitlera ich skład narodowościowy został ograniczony do przedstawicieli narodów żyjących daleko od przewidywanej granicy Wielkiej Rzeszy. Porażka wojsk niemieckich pod Moskwą zimą 1941, co przekreślało plany szybkiego pobicia Armii Czerwonej, przyśpieszyła wprowadzenie w życie decyzji dotyczących utworzenia Legionów Wschodnich. 30 grudnia 1941 do Naczelnego Dowództwa Wehrmachtu (Oberkommando der Wehrmacht) trafiło ściśle tajne memorandum, na podstawie którego miano sformować pierwsze Ostlegiony. Odpowiedzialnym za to był generał formacji wschodnich w Dowództwie Wojsk Lądowych (OKH), czyli gen. Ernst Köstring.
Legiony Wschodnie Formowanie Legionów Wschodnich rozpoczęło się już wiosną 1942. Odbywało się niemal równocześnie na obszarze Generalnym Gubernatorstwie (GG) i okupowanej Ukrainy.