Tsuboi uczył się w szkołach Yokkaichi Chūō Industrial High School i na Uniwersytecie Fukuoka. Tam też zaczął trenować piłkę nożną i m.in. w 2001 roku reprezentował Japonię na uniwersjadzie w Pekinie, którą jego rodacy wygrali dzięki zwycięstwu z Ukrainą. Po skończeniu studiów w 2002 roku Tsuboi został piłkarzem Urawy Red Diamonds i szybko przebił się do pierwszego składu zespołu. W J-League zadebiutował 3 marca 2002 w przegranym 0:1 wyjazdowym meczu z Yokohama F. Marinos. W tym samym roku otrzymał nagrody dla Debiutanta Roku w J-League, a także Młodego Zawodnika Roku. 17 maja 2003 strzelił pierwszego gola w lidze, w zremisowanym 4:4 spotkaniu z Gambą Osaka. W tym samym roku zdobył Puchar J-League. W 2005 roku wywalczył Puchar Japonii, a w 2006 swój pierwszy tytuł mistrza Japonii, a także kolejny puchar. W 2007 roku wygrał z Urawą Azjatycką Ligę Mistrzów.
