8 czerwca 2008 roku Hejduk rozegrał swój setny ligowy mecz dla Columbus Crew (przegrana 0:2 z San Jose Earthquakes).
Kariera reprezentacyjna W reprezentacji Stanów Zjednoczonych Hejduk zadebiutował 31 sierpnia 1996 roku w wygranym 3:1 spotkaniu przeciwko Salwadorowi. Pierwszego gola dla drużyny narodowej zdobył 21 grudnia tego samego roku w zremisowanym 2:2 pojedynku z Gwatemalą. Następnie Steve Sampson powołał Hejduka do 22-osobowej kadry USA na Mistrzostwa Świata 1998. Na francuskich boiskach reprezentacja Stanów Zjednoczonych zajęła ostatnie miejsce w swojej grupie i odpadła z turnieju. Sam Hejduk wystąpił we wszystkich trzech meczach, jednak tylko w spotkaniu przeciwko Iranowi rozegrał pełne 90 minut.
Później piłkarz reprezentujący jeszcze wówczas barwy Bayeru Leverkusen znalazł się w kadrze Bruce’a Areny na kolejne Mistrzostwa Świata 1998. W Korei Południowej i Japonii drużyna Stanów Zjednoczonych radziła sobie zdecydowanie lepiej niż na poprzednim mundialu. Dotarła do ćwierćfinału, w którym została wyeliminowana przez Niemców.