Fujita joined New Japan Pro Wrestling in 1993, but he still competed in amateur wrestling. Because of this his professional debut was delayed three years until 1996. His debut match was against Yuji Nagata. Fujita steadily worked his way up the card, and in 1999 he started working against professional wrestlers who came from a Vale Tudo mixed martial arts background.
In January 2000 he put his professional wrestling career on hiatus and began training for mixed martial arts competition. His trainer was his professional wrestling mentor and mixed martial arts legend, Antonio Inoki. He entered the PRIDE organization, and quickly gained success by defeating such fighters as Mark Kerr, Ken Shamrock, and Gilbert Yvel. He became known for a relentless style and his exceptionally strong neck that prevents most opponents from being able to choke him.
In April 2001 he returned to NJPW, and quickly won the IWGP Heavyweight Championship. He reigned as the champion until he was forced to vacate the title due to injury. In 2003, he memorably rocked and almost KO'd Fedor Emelianenko.
In June 2004 he defeated Bob Sapp in an MMA fight. Sapp was the current IWGP Heavyweight Champion, and the championship was vacated after his loss to Fujita. Fujita immediately won the vacated title by defeating Hiroshi Tanahashi. He lost the championship to Kensuke Sasaki on October 9, 2004.
In 2005 he joined the Team JAPAN faction, and on July 18, 2005 he won the championship for the third time. He lost it to Brock Lesnar on October 8, 2005 in a three way match including Masahiro Chono. Lesnar pinned Chono to win the title. In late 2005 he withdrew from a rematch with Lesnar, scheduled for January 4, 2006. Fujita was represented by Inoki Office, an agency originally started by Antonio Inoki, and had not been under a contract with NJPW.
|Loss||Travis Wiuff||KO (Punches)||Sengoku 3||6/8/2008||1||1:24|
|Win||Peter Graham||Submission (North/South Choke)||Sengoku||3/5/2008||1||1:23|
|Loss||Jeff Monson||Submission (Rear Naked Choke)||PRIDE 34: Kamikaze||4/8/2007||1||6:37|
|Win||Eldari Kurtanidze||Submission (Strikes)||PRIDE Shockwave 2006||12/31/2006||1||2:09|
|Loss||Wanderlei Silva||TKO (Strikes)||PRIDE Critical Countdown Absolute||7/1/2006||1||9:21|
|Win||James Thompson||KO (Punch)||PRIDE Total Elimination Absolute||5/5/2006||1||8:25|
|Win||Karam Ibrahim||KO (Punch)||K-1 - Premium 2004 Dynamite||12/31/2004||1||1:07|
|Win||Bob Sapp||Submission (Strikes)||K-1 MMA - ROMANEX||5/22/2004||1||2:15|
|Win||Imamu Mayfield||TKO (Arm Triangle Choke)||Inoki Bom-Ba-Ye 2003 - Inoki Festival||12/31/2003||2||2:15|
|Loss||Fedor Emelianenko||Submission (Choke)||PRIDE 26: Bad to the Bone||6/8/2003||1||4:17|
|Win||Manabu Nakanishi||TKO||NJPW - Ultimate Crush||5/2/2003||3||1:09|
|Loss||Mirko Filipovic||Decision (Unanimous)||Inoki Bom-Ba-Ye 2002 - K-1 vs. Inoki||12/31/2002||3||5:00|
|Win||Tadao Yasuda||Submission (Arm Triangle Choke)||UFO - Legend||8/8/2002||1||2:46|
|Loss||Mirko Filipovic||TKO (Cut)||K-1 - Andy Hug Memorial||8/19/2001||1||0:39|
|Win||Yoshihiro Takayama||Submission (Choke)||PRIDE 14 - Clash of the Titans||5/27/2001||2||3:10|
|Win||Gilbert Yvel||Decision||PRIDE 12: Cold Fury||12/9/2000||2||5:00|
|Win||Ken Shamrock||TKO (Corner Stoppage)||PRIDE 10||8/27/2000||1||6:46|
|Loss||Mark Coleman||TKO (Corner Stoppage)||PRIDE Grand Prix 2000 Finals||5/1/2000||1||0:02|
|Win||Mark Kerr||Decision||PRIDE Grand Prix 2000 Finals||5/1/2000||1||15:00|
|Win||Will Childs||Submission (Rear Naked Choke)||Extreme Shootout - The Underground||4/1/2000||N/A|
|Win||Dan Chase||KO||Extreme Shootout - The Underground||4/1/2000||N/A|
|Win||Hans Nijman||Submission (Choke)||PRIDE Grand Prix 2000 Opening Round||1/30/2000||1||2:48|