On June 12, 2004 in AJPW, Nakajima received the first championship match of his career, teaming with Kensuke Sasaki to unsuccessfully challenge Masanobu Fuchi & Genichiro Tenryu for the All Asia Tag Team Championship. On September 17, 2004, Nakajima made his debut in Dragon Gate on their pay-per-view "Gate of Sanctuary", losing to Masaaki Mochizuki. 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. 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.