9 listopada 1996 bronił mistrzostwa WBA w walce przeciwko Evanderowi Holyfieldowi, który pokonał go technicznym nokautem w jedenastej rundzie. Była to druga przegrana Tysona w jego karierze. Walka rewanżowa Tysona i Holyfielda miała miejsce 28 czerwca. Tym razem Tyson został zdyskwalifikowany za dwukrotne ugryzienie przeciwnika w ucho. W związku z tym incydentem musiał zapłacić 3 miliony dolarów i na jakiś czas odebrano mu bokserską licencję. Tyson tłumaczył, że ugryzienie ucha było odwetem za to, że Holyfield uderzył go głową powyżej oka. Sędzia Mills Lane uznał jednak, że uderzenie było przypadkowe. Wiele lat później Tyson przyznał, że w czasie drugiej walki z Holyfieldem był pod wpływem narkotyków.
W czerwcu 2000 pokonał już w 38 sekundzie pierwszej rundy swojego rodaka Louisa „Lou” Savarese’a. Bezsilny przeciwnik byłego absolutnego mistrza świata padł na matę już po 15 sekundach walki. Następnie „Żelazny Mike” uderzył również sędziego, który miał pecha znaleźć się w jego „zasięgu”. Po wznowieniu walki, Tyson zademonstrował serię ciosów w twarz i korpus, po czym sędzia przerwał walkę.
W październiku 2000 walczył z Andrzejem Gołotą.