A szerb családból származó Sztójay – még Dimitrije Sztojakovics néven – 1883-ban, Versecen született. Katonai pályáját a Monarchia hadseregében kezdte, ezredesként harcolt az első világháborúban és a magyar Vörös Hadseregben, majd a Horthy-féle nemzeti hadsereg kémelhárító osztályán. A húszas évek elején léptették elő tábornokká, 1925-ben pedig Berlinbe került, mint katonai attasé; ekkor változtatta nevét Sztojakovicsról Sztójayra. 1933-ban hazahívták, két évig a Honvédelmi Minisztériumban alkalmazták, majd 1935-ben Gömbös Gyula őt nevezte ki berlini magyar követnek – ekkor már altábornagy.
Követi pozícióját egészen 1944-ig, miniszterelnöki kinevezéséig megtartotta, és ebben a kilenc évben mindent megtett azért, hogy Magyarországot a német-olasz tengely mellé állítsa.