Az 1980-as években Minszk városában nem sok szórakozási lehetőségük volt a gyerekeknek, maximum a sport jelenthetett valamiféle kitörési lehetőséget a szegénységből, nem csoda, hogy az 1981. május elsején született Alekszander Hleb is ezzel próbálkozott.
A srác, akinek édesapja kamionsofőrként, édesanyja pedig kőművesként (az egykori Szovjetunióban nem volt ritka, hogy a nők is férfias munkákat végeztek, gondoljunk csak a traktoros lányokra) dolgozott, az úszással és a tornával is próbálkozott, de végül a futballnál kötött ki, és már hatesztendősen a Dinamo Minszkben kergette a labdát. Persze ne gondoljunk a mai futballakadémiákra jellemző körülményekre: a minszki fiatalok csak aszfalton futballozhattak, ami meglehetősen sérülésveszélyes volt, arról nem is beszélve, hogy ennek köszönhetően meglehetősen gyakran kellett új cipőt venniük.
Hleb édesapja meglehetősen sokat volt távol otthontól, megfordult például Csernobilban is, ahol az atomkatasztrófa után a lakhatatlanná vált házak lerombolásában vett részt - a család szerint minimális szinten ő is megérezte a sugárfertőzés hatását, még ha komoly betegsége nem is lett. A família a vasfüggöny ledőlését követően egy kicsit jobb körülmények között élt, de a kis Alekszandr szerint túl nagy változást nem hozott a dolog - leginkább az hatott rá, hogy a papa az egyik nap egy videomagnóval tért haza.
Ami pedig a focit illeti, a korábban Fehéroroszországban egyeduralkodónak számító minszki Dinamo egyre lejjebb csúszott a ranglétrán, így Hleb örömmel fogadta, amikor az egyik feltörekvő egyesület, a BATE Boriszov bejelentkezett érte. A fiatal középpályás mindössze 17 esztendős volt, amikor a boriszovi klubhoz igazolt, és egy évvel később már be is mutatkozhatott az élvonalban - és a negyedik fordulóban megszerezte első találatát. Ennél többet ugyan nem ért el, de az év végén így is bajnoki címet ünnepelhetett.
Sokáig azonban nem maradt Fehéroroszországban, hiszen miután a 2000-es pontvadászat első felében már rendszeresen szerepelt a BATE csapatában, a bajnokság közben, vagyis a nyugat-európai holtszezonban Németországba utazott próbajátékra. Először az 1860 München tesztelte, de az Oroszlánok akkori mestere, Werner Lorant úgy ítélte meg, hogy a kétségtelenül ügyes srác nincs olyan fizikális állapotban, hogy megállja a helyét a Bundesligába.
Stuttgartban azonban máshogy gondolták, és amatőr szerződést ajánlottak a középpályásnak. Hleb eleinte nem érezte valami jól magát Németországban: egyedül volt egy idegen helyen, és szinte senkivel sem tudott kommunikálni, hiszen ő csak oroszul beszélt - ezt a nyelvet pedig kevesen bírták Svábföldön. A srácot a nagycsapat karmestere, Kraszimir Balakov vette pártfogásába, hiszen ő meg tudta értetni magát vele, és Hleb lassacskán kezdett beilleszkedni a klubnál. Az első idényben azért többnyire a harmadosztályban, a tartalékcsapatban játszott (amelyben rajta kívül olyan focisták szerepeltek, mint Kevin Kuranyi, Christian Tiffert, Joannisz Amanatidisz vagy Markus Miller), de azért hat találkozón a felnőttek között is becserélték.
A fordulópontot a 2001-2002-es idény negyedik fordulója jelentette. A VfB Stuttgart akkor Nürnbergben lépett pályára, és Felix Magath mester némi meglepetésre a kezdők közé jelölte Hlebet - aki a mérkőzés legjobbjának bizonyult, három gólpasszt is adott. Ettől kezdve már folyamatosan játéklehetőséget kapott, és ha ezt a teljesítményt nem is tudta mindig megismételni, de további három asszisztot adott, és kétszer maga is eredményes volt. A következő idényben pedig még ezt is felülmúlta: góljainak számát megduplázta, eggyel több gólpasszt is adott, de ami még fontosabb, a megfiatalított Stuttgart Kuranyival, Tifferttel, Hinkellel és Timo Hildebranddal (a csapatot Németországban csak Vad Ifjaknak becézték) ezüstérmes lett a Bundesligában, amivel kiharcolta a BL-részvételt.