Hivatásos labdarúgói pályafutását 18 évesen, 1995-ben kezdte a japán ligában a Bellmare Hiracuka (ma Sónan Bellmare) csapatában.
A franciaországi világbajnokság után a Serie A-ban szereplő Perugia-hoz szerződött. Nakata volt a második japán labdarúgó Miura Kazujosi után, aki az olasz bajnokságban játszhatott. Első idényében 10 gólig jutott.
2000 januárjában, a Perugiában eltöltött másfél év után, Nakata az AS Romában folytatta pályafutását. Csapatával megnyerte a bajnokságot: a Juventus elleni 2001. május 6-ai mérkőzésen, Francesco Totti cseréjeként beállva 0–2-es állásnál szépített és az egyenlítő gólból is kivette a részét. 2001-től két és fél éven keresztül Parmaban futballozott.
2004 januárjában kölcsönben a Bologna játékosa lett, ahol a 2003–04-es idény hátralévő részét töltötte. A következő szezonban már a Fiorentina csapatát erősítette.
A 2005–06-os szezonban kölcsönben az angol bajnokságban szereplő Bolton Wanderersben játszott.