Leopold Wilhelm von Edelsheim néven született, de amikor gróf Gyulai Ferenc és Antonia Wratislav-Mitrowsky grófnő adoptálták, magyarosította a nevét. Alig lehetett 16 éves, amikor belépett a Császári-Királyi Hadseregbe (Kaiserlich-Königliche Armee), és részt vett a magyarországi hadjáratban. Ezalatt főhadnagyi rangban Windischgrätz alatt küzdött a bábolnai, a móri és a szolnoki csatában is. A későbbiekben Magenta és Solferino csataterein a 10. huszárezred vezetőjeként jeleskedett. A háború után fegyvernemének egy a speciális magyar lovasságiéhoz hasonló szabályzatot szerkesztett. Ezen szabályzat annyira bevált, hogy később Európa majdnem összes hadseregénél használták. Az 1866. évi königgrätzi csatában való helytállásáért altábornaggyá nevezték ki. 1869-ben a lovasság főfelügyelője lett, 1874-ben pedig Magyarország főhadparancsnoka.
1886-ban Janszky Lajos tábornok ügye miatt Edelsheim-Gyulai nyilatkozatot adott ki, s ezt még Tisza miniszterelnök is megemlítette a képviselőházban. Ezt követően Edelsheim-Gyulait nyugdíjazták, mely valószínűleg az említett nyilatkozat miatt történt. Nyugdíjazása rendkívüli módon emelte népszerűségét. Ezek után a fővárosi társasélet egyik kiemelkedő alakja lett. 1893-as halálhíre nagy részvétet keltett az egész országban.
Címei, kitüntetései
a császári és királyi hadsereg főhadnagya (1842-től)
huszárezred-parancsnok
altábornagy (1866-tól)
lovassági főfelügyelő (1869-től)
főhadparancsnok (1874-től)
báró (1882-től)
Családja
Felesége, Friderika Kronau (1841-1918) egyetlen gyermeket szült neki:
Lipót József (1863-1928), felesége: szerémi herceg Odescalchi Irma Paulina Anna Ilona
