Erdei Zsolt 1974. május 31-én látta meg a napvilágot, Budapesten. Édesapja Ernei Ernő, édesanyja Bartha Gizella volt. Egy nővére és két húga van.
A szülei házassága végleg megromlott, amikor Zsolt 9 éves lett, azt követően édesapja csupán egy alkalommal látogatta meg őt a válás után. Édesanyjának idővel új társa lett, azonban sajnos ez a kapcsolat sem volt fenékig tejfel. Megesett, hogy a férfi bántotta az anyát, a 18 éves Zsolt pedig éppen akkor ért haza és egy pofon kíséretében megfékezte a nevelőapját. Ezt követően az asszony egyedül nevelte a gyermekeit.
1992-ben kezdte meg a középiskolás éveit a Csanádi Árpád Központi Sportiskolában.
2005-ben feleségül vette a spanyol-osztrák származású Arabella Del Mar Stanzig-ot.
2006-ban Erdei Zsolt első felesége, Arabella közös gyermeküknek adott életet, akit Erdei Viktornak neveztek el.
2012-ben, 7 év házasság után úgy döntöttek, hogy felbontják a házasságukat.
2013-ban Zsolt beleszeretett Dudás Rékába.
2014-ben született meg első közös gyermekük Gréta, aki koraszülöttként a vártnál korábban érkezett.
2015-ben Zsolt édesanyja hosszú, türelemmel viselt betegség után elhunyt. Az egykori bokszoló nagyon szoros kapcsolatot ápolt az vele, ezért rendkívül nehezen viselte az elvesztését.
2017-ben született meg Réka és Zsolt harmadik gyermeke, Vilmos.
2024-ben kiderült, hogy Erdei Zsolt fiának, Vilmosnak kiváló zenei tehetsége van: rappelni kezdett és még ebben az évben megjelent első önálló videoklipje.
1995-ben kezdte meg Erdei Zsolt ökölvívói pályafutását a 75 kg-os mezőnyben. Amatőr bokszolóként 212 győzelmet aratott és csupán 20 meccsen maradt alul.
Eleinte Szakos József és Fehér Mihály voltak a nevelőedzői.
Később Klein Csaba, majd Fritz Sdunek edzette Zsoltot.
1997. október 25-én, Budapeste vívta egyik legjobb mérkőzését, amikor Ariel Hernández-zel szállt egy ringbe.
2000. november 6-án került be a profi ökölvívók közé, amikor bekerült az Universum Box-Promotion versenyzői közé. Több mint 5 éven át versenyzett a klub képviseletében, mint a WBO félnehézsúlyú világbajnoka.
Ekkoriban már a Republic együttes - Szállj el kismadár című dalára vonult a ringhez. Ezért is kapta Erdei Zsolt a Madár becenevet.
2009. november 21-én, egy súlycsoport váltást követően elnyerte a WBC cirkálósúlyú világbajnoki övét. A német klubbal való szerződése 2010 júniusáig volt érvényben.
2010 nyarán a világ egyik legnevesebb menedzserével, Lou DiBellával, kötött szerződést, melyben belefoglalták, hogy 3+2 meccset fog játszani. Erdei Zsolt a keresett promóter segítségével próbált nevet szerezni az amerikai bokszban.
2011 őszén egy kézsérülés miatt lemondta a december 31-ei Tavoris Cloud elleni IBF világbajnoki címmeccset.
2013. március 30-án ringbe szállt az egykori orosz származású kick-box-os Gyenyisz Gracsovval. Zsolt sajnos alulmaradt a küzdelemben.
2014. március 8-án a grúz Salva Dzsomardasvili ellen győzött, ezzel megszerezte a WBO Európa-bajnoki címet.
Ezt követően bejelentette, visszavonul a profi ökölvívástól.
2017-ben megválasztották a Magyar Ökölvívó-szakszövetség elnökének.
2020-ban bejelentette, hogy lemond a szakmai társelnöki posztjáról.
2024-ben védnökként volt jelen a Police Fight Challenge elnevezésű jótékony célú rendezvényen. A program céljaként azt tűzték ki, hogy a szolgálatteljesítés során megsérült rendvédelmi dolgozóknak, illetve a szolgálatteljesítés közben életüket vesztő rendőrök családjainak és a közvetlen hozzátartozóinak nyújtanak támogatást.
2002-2003 - WBO félnehézsúlyú interkontinentális bajnok
2004-2009 - WBO félnehézsúlyú világbajnok
2009 - WBC cirkálósúlyú világbajnok
2014 - WBO félnehézsúlyú Európa-bajnok
34 győzelem - 1 vereség - 18 KO/TKO
2017 - Budapest Noir
2007 - A Magyar Köztársasági Érdemrend tisztikeresztje
2010 - Prima díj
2011 - Budapestért díj
2014 - Csik Ferenc-díj
2014 - Nemzeti Sport karrier díj