Haye started his career as an amateur. He reached the finals of the 2001 world amateur championship in the heavyweight class, where he lost to Odlanier Solis. He turned professional in the cruiserweight division in December 2002. His first professional fight was meant to be against Valeri Semishkur, but Semishkur pulled out. Instead, Haye fought and beat Tony Booth on 8 December 2002. He had seven fights in 2003, and won all of them. He won his tenth fight in a row when he beat Arthur Williams on 12 May 2004. He won those ten fights with a total of only 20 rounds. In his match against IBO champion Carl Thompson on 10 September 2004, he lost for the first time in his career. In his next match, on 10 December 2004, he beat Semishkur in the first round.