S profesionálnym hokejom začínal v Pardubiciach. V roku 1994 bol draftovaný klubom Quebec Nordiques. V NHL však hrá až od sezóny 1998/1999 za tím Colorado Avalanche. K jeho najväčším úspechom patrí zisk Stanley Cupu v roku 2001, zisk Maurice Richard Trophy pre najlepšieho strelca NHL. Na domácej scéne získal titul s Pardubicami roku 2005. Bol členom úspešného výberu na ZOH v Nagane (1998), kde nastúpil až v troch zápasoch play-off a pomohol vybojovať historicky prvú zlatú medailu pre Český hokejový tím. V posledných sezónach nosil na drese kapitánske "C".
Česko získalo na Zimných olympijských hrách 2006 bronzové medaily. Úvod olympiády českej reprezentácii nevyšiel, keď v základnej skupine skončila až na štvrtom, poslednom postupovom mieste, po prehrách so Švajčiarskom 2:3, Fínskom 2:4 a Kanadou 2:3. Vo štvrťfinále Česko vyradilo Slovensko. V semifinále ich vyradili neskorší zlatí medailisti Švédi a v boji o bronzové medaily porazili Rusko 3:0. Milan Hejduk bol s piatimi mínusovými bodmi najhorší hráč svojho mužstva v +/- hodnotení.
