In Tua's 1997 fight against Ike Ibeabuchi, the two fighters combined to set the record for most punches thrown in a heavyweight fight on record. Ibeabuchi won the decision, handing Tua his first professional loss. Prior to this, Tua had scored devastating knockouts against future titlist John Ruiz (via 1st-round KO, in only 19 seconds) and Darroll Wilson. Tua also beat David Izon and future champion Oleg Maskaev to set up the fight with Ibeabuchi. After the loss to Ibeabuchi, Tua took on future champ Hasim Rahman and TKO'd Rahman in the 10th round. The victory over Rahman marked the beginning of Tua's struggles with his weight. He ballooned up to 253 pounds when he defeated Obed Sullivan in 2000 by KO. Later that year, he weighed 245 pounds in the loss to Lennox Lewis. Tua was disappointing in the fight, with both fighters avoiding each other and Tua not throwing combinations. Tua lost a clear-cut decision.