Otázka vytvorenia autonómneho čs. zahraničného vojska, ktoré by bojovalo po boku vojsk Dohody proti Nemecku a Rakúsko-Uhorsku, ako rozhodujúceho prejavu vôle Čechov a Slovákov po národnej slobode a prvého kroku uznania budúceho samostatného Česko-slovenského štátu, bola od začiatku jedným z najdôležitejších cieľov ČSNR. Vychádzalo sa pritom z koncepcie zajateckej akcie, ktorá si našla nielen podporu vo vojenských kruhoch Francúzska, ale aj na jeho ministerstve zahraničných vecí. Štefánik pri vzniku československých légií zohral rozhodujúcu úlohu. Predložil francúzskej armáde návrh na vytvorenie samostatnej čs. jednotky. Od apríla 1916 pôsobil v Taliansku a dal výrazný impulz k letákovej akcii, v ktorej nabádal slovanských vojakov rakúsko-uhorskej armády k prebehnutiu na taliansku stranu. Podarilo sa mu získať významné kontakty medzi talianskou politickou elitou. V júli 1916 bol Štefánik francúzskou vládou vyslaný do Rumunska a Ruska, kde rokoval v rámci tzv. ,,zajateckej akcie" o nábore čs. dobrovoľníkov z radov zajatcov pre francúzsky front. Misia sa však zmenila na zápas za jednotu čs. odboja. Keď sa však Štefánik začiatkom roku 1917 opäť do Ruska vrátil, inicioval tzv. Kyjevský zápis. Po februárovej revolúcii 1917 v Rusku sa mu s predstaviteľmi novej dočasnej ruskej vlády podarilo dohovoriť hlavné princípy formovania česko-slovenského vojska a taktiež dosiahol uznanie ČSNR za jedinú predstaviteľku čs. odboja v zahraničí. Po známej Zborovskej bitke 2. júla 1917, sa z pôvodnej Českej družiny začala postupne vytvárať najmasovejšia vojenská zložka prvého čs. zahraničného odboja – Československý zbor v Rusku. 

Od mája 1917 Štefánik v USA organizoval nábor do légií vo Francúzsku. Tie vznikli na základe prezidentského dekrétu Raymonda Poincaré o čs. armáde z 19. decembra 1917, ktorý pripravili s E. Benešom a štatútu zo 7. februára 1918. V apríli 1918 Štefánik uzavrel dohodu o vzniku čs. légií v Taliansku a podieľal sa na ich vzniku. V máji 1918 vypukol v Rusku konflikt légií s boľševikmi. Légie ovládli 8000 kilometrov sibírskej magistrály a na základe toho uznali dohodové veľmoci ČSNR za predstaviteľku budúceho štátu. Potom však nastala dezilúzia. V kritickej situácii v novembri 1918 prišli na Sibír generál a minister vojny Štefánik a hlavný veliteľ sibírskych spojeneckých vojsk francúzsky generál Janin. Štefánik nariadil stiahnuť légie z frontu a v januári 1919 generáli dohodli ich odchod do zázemia. Vo februári 1919 sa generál Štefánik vrátil do Európy a od polovice marca sa už ako československý minister vojny krátko zúčastnil na mierových rokovaniach v Paríži. Popritom vynaložil maximálne úsilie, aby sa urýchlil návrat čs. légií z Ruska do vlasti. Rokoval s najvýznamnejšími predstaviteľmi Dohody, na čele s maršalom Ferdinandom Fochom, o konkrétnych otázkach postupného odsunu legionárov zo Sibíri. 28. apríla 1919 vykonal na vojenskom cvičisku Gollasecca v Gallarate prehliadku čs. domobraneckých práporov.