On May 7, 2005, Katsuhiko participated in the 2005 Differ Cup, a biennial cross-promotional junior heavyweight tag team tournament, teaming with Osaka Pro's Takehiro Murahama; the two lost to Super Shisa and Tiger Emperor in the first round. He also teamed with Tomoaki Honma in a tournament throughout June 2005 to decide the vacant All Asia Tag Team Championship, making it to the finals before losing to Shuji Kondo & "brother" YASSHI. Just over one month later on July 26, 2005, Nakajima and Kensuke Sasaki defeated Kondo and YASSHI for the titles in their second defense, giving Nakajima his first championship. They would continue to defend the titles through 2005, against such teams as Arashi & Ryuji Hijikata and Buchanan & D'Lo Brown.