Když se nejslavnější generál československých legií v Rusku a našich legií vůbec vracel lodí koncem r. 1919 z Vladivostoku do vlasti, byl na svých zastávkách vítán předními politiky jako vynikající voják, který se zasloužil nejen o svou vlast, tehdy vzniklou Československou republiku, ale jenž se proslavil i v boji proti bolševikům také na straně bělogvardějců. Kdyby se byl tehdy Gajda hodlal zastavit i v Anglii, musel by mu naproti vyplout torpédoborec s členem královské rodiny na palubě, jak to příslušelo nositeli jednoho z nejvyšších anglických řádů, jímž generál Gajda byl. Když však „sibiřský hrdina“ přijel z Paříže na pražské hlavní nádraží, vítala ho jen hrstka spolubojovníků. Měl totiž mocného nepřítele, samotného státního prezidenta ČSR Masaryka, kterého si znepřátelil již během první světové války v Rusku tím, že v rozporu se zástupci moskevské Odbočky Československé národní rady, jejíž zástupci se dohodli na vydání větší části zbraní legionářů bolševikům, tedy i v rozporu s intencemi Masaryka, odmítl vydat tyto zbraně a v případě nutnosti se vlastními silami probít podél sibiřské magistrály do Vladivostoku, kde měly být československé legie naloděny a převezeny na frontu do Francie. „Sibiřským hrdinou“ byl nazýván právě proto, že se mu v průběhu slavné „sibiřské anabáze legií“ podařilo docílit řady vynikajících vítězství nad bolševiky a splnit své poslání.