He debuted for World Japan (WJ) in September 2003, facing American fighter Jason Leigh in an MMA fight, winning via knockout in one minute and thirty-five seconds.

[4] His true professional wrestling debut came on the main event of World Japan's "Resolution" card on January 5, 2004, losing via submission to Tomohiro Ishii.

[12] This led to his debut with New Japan Pro-Wrestling, facing legendary junior heavyweight Jushin Thunder Liger in the Tokyo Dome on May 3, 2004.

[16] The following month, Nakajima entered the Osaka Pro Tenno-zan single-elimination tournament, losing to eventual winner Big Boss MA-G-MA in the first round.

[17] Nakajima and Sasaki teamed up in the World's Strongest Tag Determination League in November and December 2004, finishing with four points in Block B.

[18] Nakajima received his first opportunity at a singles championship on April 20, 2005, losing to World Junior Heavyweight Champion Taka Michinoku.

[19] His appearances in NJPW became much more sporadic around this time, with his final match to date taking place on April 24, 2005, a loss to 6-time IWGP Heavyweight Champion Tatsumi Fujinami.

[29] On March 21, 2006, Nakajima won a three-way elimination match in AJPW, defeating both Tomoaki Honma and Nosawa Rongai to earn a spot in Block B of the prestigious 2006 Champion Carnival,[30] becoming the youngest man to participate in the tournament.

[34] On October 15, 2006, Katsuhiko Nakajima and Kaz Hayashi were announced as one of seven teams in the 2006 World's Strongest Tag Determination League, to take place in December 2006.

They had a strong showing in the tournament, defeating such teams as Nosawa Rongai and Triple Crown Heavyweight Champion Minoru Suzuki and RO'Z and Suwama and drawing with Taiyō Kea and Taka Michinoku, finishing with 5 points overall.

[37] Nakajima made his first defense of the title on April 30, 2007, defeating Kondo's Voodoo Murders partner "brother" Yasshi,[38] as well as Ryuji Hijikata on May 27, 2007.

[42] On September 1, 2007, Nakajima challenged Pro Wrestling Noah's Takeshi Morishima for his ROH World Championship in the main event of a Kensuke Office show, putting up a good fight but losing in the end.

[46] On March 1, 2008, in a rematch from their October encounter, Nakajima lost to Silver King in a match to decide the vacant junior heavyweight title.

[48] On March 28, 2008, Nakajima faced and defeated Osaka Pro and Dragon Gate wrestler Magnitude Kishiwada on Kensuke Office's first event in the Fukuoka region.

[49] On May 25, 2008, in AJPW, Nakajima and Sasaki lost to Taiyō Kea and Minoru Suzuki in a match to determine the #1 contenders to the World Tag Team Championship.

On September 14, 2008, Nakajima participated in American promotion Ring of Honor's second tour of Japan, teaming with Naomichi Marufuji against Kenta and Kota Ibushi in a special tag match.

[55] The following week on September 20, Nakajima wrestled his first match in the United States, challenging GHC Junior Heavyweight Champion Bryan Danielson at ROH's Glory by Honor VII.

Nakajima along with his mentor Kensuke Sasaki reached the Pro Wrestling Noah Global Tag League final in 2013, but lost to the team of Kenta and Yoshihiro Takayama.

On February 11, 2014, Nakajima earned his first win over his mentor Kensuke Sasaki in the main event of a show celebrating his tenth anniversary in professional wrestling.

On December 24, 2015, Noah held a press conference announcing that Nakajima would be ending his days as a freelancer and officially joining the promotion on January 1, 2016.

[58] On February 24, 2016, Nakajima picked up the biggest win of his career by defeating Minoru Suzuki in the main event of Noah's show in Korakuen Hall.

[60] From July 22 to August 13, 2016, Nakajima took part in NJPW's 2016 G1 Climax, where he finished tied third in his block with a record of five wins and four losses, failing to advance to the finals.

[62] Nakajima made his first title defense in a match against the 2016 Global League winner, Minoru Suzuki, at One Night Cruise in Korakuen on December 2.

Naomichi Marufuji and Akitoshi Saito vacated the GHC Tag Team Championship on November 28, a tournament to decide the new champions happened on December 7.

Afterwards, Axiz began focusing on their singles careers, after Nakajima defeated Daiki Inaba to win the Wrestle-1 Championship on January 12 as part of a working relationship between Noah and Wrestle-1.

On August 20, Axiz faced Sugiura-gun (Kazushi Sakuraba and Takashi Sugiura) in a losing effort for the vacant GHC Tag Team Championship.

On March 7, 2021, at Great Voyage in Yokohama, Nakajima and Kitamiya defeated Sugiura-gun's Kazushi Sakuraba and Takashi Sugiura to win the GHC Tag Team Championship for the third time.

On October 3, Nakajima defeated Masakatsu Funaki and then fellow Kongo stablemate Kenoh, in the semifinals and finals, respectively, to win the N-1 Victory for the second year, earning a shot at the GHC Heavyweight Championship.

Afterwards, Go Shiozaki made his return from injury challenging his former Axiz teammate Katsuhiko Nakajima to a title match for the GHC Heavyweight Championship on January 1, at Noah The New Year.

He departed Pro Wrestling Noah in October 2023, citing that he "wanted to challenge himself", as well as believing that 35 is a major crossroads in many peoples' lives.