Ezzel együtt az immár az U21-es válogatottban is rendszeresen szereplő Gallas egyre elismertebb focista lett, és ehhez a következő szezonban a Bajnokok Ligájában nyújtott teljesítménye is hozzájárult. A Marseille-nek sikerült továbbjutnia az első csoportkörből a BL-ben, és a Manchester United elleni hazai mérkőzésen Gallas megszerezte pályafutása első gólját a felnőttek között: a hátvéd váratlanul előretört, amivel az angol védők nem tudtak mit kezdeni, lövését pedig Mark Bosnich érdekes mozdulattal, fejjel akarta hárítani, ám ez nem sikerült neki.
A kiváló formában lévő bekk, aki ebben az időszakban már leginkább a védelem tengelyében játszott, egyre közelebb került a nagyválogatotthoz is, azonban 2000 februárjában lábtörést szenvedett, és így ki kellett hagynia a bajnokság hátralévő részét - aminek köszönhetően az Eb-n való szereplésről is lemondhatott.
2000 nyarán egyébként több klub is hívta Gallast, leginkább a Girondins Bordeaux csábította, de a hátvéd a maradás mellett döntött - ami rossz választásnak bizonyult. Pedig az idény jól indult, William rögtön az első fordulóban megszerezte pályafutása első bajnoki találatát, de a szezon közben érkezett új tréner, a spanyol Javier Clemente ismét jobbhátvédként szerette volna őt számításba venni, mire a focista kijelentette, hogy ő csak középhátvédként hajlandó pályára lépni.
A klub egy hónapra a tartalékok közé száműzte a renitens játékost, ám mivel a téli átigazolási időszakban senki sem jelentkezett be érte, így februárban visszatért az első csapat keretéhez. Ezt az egy hónapos kihagyást leszámítva Gallas végig alapember volt az OM-ben, de sejteni lehetett, hogy a következő idényt már nem Marseille-ben fogja kezdeni.