Pierwsze treningi drużyna rozpoczęła wiosną 1915 roku w Piotrkowie, natomiast między 5 a 15 marca 1916 – na wniosek chorążego Zygmunta Wasseraba (przedwojennego piłkarza klubu Pogoń Stryj) – w kancelarii kompanii sztabowej Komendy Legionów Polskich w Kostiuchnówce (znajdującej się niedaleko Maniewicz na Wołyniu) doszło do założenia klubu piłkarskiego. Na prezesa organizacji mianowano chorążego Władysława Groelego, a plutonowy Stanisław Mielech zaproponował nazwę „Drużyna Sportowa Legia”, która została przyjęta. Innymi propozycjami nazwy były: „Drużyna Komendy Legionów” oraz „Styr”Rzeka leżąca niedaleko komendy.. Przyjęto również biało-czarne barwy i herb ukazujący białą literę „L” (symbol Legionów) na czarnej tarczy. Piłkarze grali w białych strojach z ukośnymi czarnymi pasami, co było nawiązaniem do drużyny Czarnych Lwów.
Na wiosnę 1916 roku zespół rozegrał szereg meczów z innymi drużynami żołnierskimi, które w większości zakończyły się zwycięstwami Legii. Najstarsze zachowane wyniki meczów to: 7:0 z Dywizyjnym Zakładem Sanitarnym, 3:3 z 6. Pułkiem Piechoty Legionów oraz dwa zwycięstwa (6:4 i 3:1) z 4. Pułkiem Piechoty Legionów. W lipcu 1916, w związku z Ofensywa Brusiłowa, Legiony rozpoczęły odwrót na zachód;