Felnőtt pályafutását 1995-ben kezdte a 75 kg-os mezőnyben, amatőrként 20 vereség mellett 212 győzelmet könyvelhetett el.
Nevelőedzői Szakos József és Fehér Mihály voltak, később Klein Csaba, majd Fritz Sdunek vezetésével ért el sikereket.
Legjobbnak tartott mérkőzését Budapesten, 1997. október 25-énAriel Hernández ellen vívta. Profi pályafutását 2000. november 6-án kezdte, az Universum Box-Promotion versenyzőjeként. A hamburgi klub színeiben több, mint öt évig volt a WBO félnehézsúlyú világbajnoka. A német istálló menedzselésében 2009. november 21-én lépett utoljára a ringbe, amikor is – súlycsoportváltást követően – a WBC cirkálósúlyú világbajnoki övét is elhódította; szerződése 2010 júniusában járt le. Ugyanazon év nyarán három plusz két mérkőzésre szóló megállapodást kötött a világ egyik leghíresebb promóterével, Lou DiBellával, akinek segítségével megpróbált az amerikai bokszpiacra betörni. Sorozatos sérülései miatt 2011 őszén úgy döntött, egy ideig felhagy az ökölvívással.
2013. március 30-án visszatért az aktív bokszolók világába és ringbe szállt az egykori kick-box-os Gyenyisz Gracsovval – a találkozót Zsolt elvesztette.[2]
2014. március 8-án a grúz Salva Dzsomardasvili legyőzésével megszerezte a WBO Európa-bajnoki címét, majd bejelentette visszavonulását.[3]
Profi karrierje elején a népszerű német Scooter együttes Don't let it be me, később pedig a magyar Republic együttes Szállj el kismadár című dala volt a bevonulózenéje.
2017 áprilisában a Magyar Ökölvívó-szakszövetség elnökének választották.[4]
2020 augusztusában a szakmai társelnöki posztjáról lemondott.[5]
Profi eredményei
WBO félnehézsúlyú interkontinentális bajnok (2002–2003)
2005 és 2012 között a spanyol-osztrák származású Arabella Del Mar Stanziggal élt házasságban.[8][9] Fiuk, Viktor 2006-ban született.[10] 2013 óta párja Dudás Réka, kislányuk, Gréta 2014 májusában, a vártnál jóval korábban jött a világra.[11][12] Harmadik gyermeke, Vilmos 2017-ben született.[13]
Deák Zsigmond–L. Pap István–Moncz Attila: Madár. "Szállj messze, szállj magasra!". Erdei Zsolt útja a világbajnoki címig; Aréna 2000, Bp., 2004
Szegő András: Madár. 12 menet Erdei Zsolttal; Kossuth, Bp., 2010
McMenemy Márk: Daddy cool. Vagányok és apák. Dragomán György, Erdei Zsolt Madár, Halácsy Péter, Kiss Tibi, M. Kiss Csaba, Nánási Pál, Somlai-Fischer Ádám, S. Takács András, Szabó Győző, Zsiday Roy; fotó Boncsér Orsolya; Zazie Books, Bp., 2016