W 1999 roku stoczył dwie walki z Evanderem Holyfieldem, mistrzem organizacji IBF i WBA. W pierwszej, która odbyła się 13 marca, ogłoszono niejednogłośny remis (113-116, 115-113, 115-115). W drugiej (13 listopada) Lewis pokonał Holyfielda przez jednogłośną decyzję (116-112, 117-111, 115-113). Brytyjczyk zunifikował tym samym mistrzostwo świata w wadze ciężkiej, zdobywając tytuły WBC, WBA, IBF i mniej znaczącej organizacji IBO.
W kwietniu 2000 WBA pozbawiła jednak go tytułu za odmowę walki z Johnem Ruizem. Lewis wolał wybrać pojedynek z ówcześnie wyżej notowanym Michaelem Grantem, którego znokautował w 2. rundzie broniąc 29 kwietnia 2000 tytuły WBC, IBF i IBO. W kolejnych dwóch obronach znokautował Fransa Bothę (lipiec 2000) i pokonał na punkty Davida Tuę (listopad 2000).
Swoją drugą i ostatnią porażkę w zawodowej karierze poniósł niespodziewanie 22 kwietnia 2001 roku w starciu z Hasimem Rahmanem. Został znokautowany prawym sierpowym w piątej rundzie i utracił swoje trzy mistrzowskie pasy. Zaraz po ogłoszeniu wyniku zażądał rewanżu, który był zagwarantowany w kontrakcie. Obaj zawodnicy spotkali się ponownie w ringu siedem miesięcy później w Las Vegas. Tym razem Lewis znokautował Amerykanina w czwartej rundzie, odzyskując tytuły.