Tulio made his debut for the Japan's senior national team on 9 August 2006, against Trinidad and Tobago. He scored his first goal for Japan on 15 November 2006 in a 2007 AFC Asian Cup qualifier against Saudi Arabia. After the strong performance in 2006 season, which led Urawa to win their first ever J. League Division 1 title, he received J-League Player of the Year. But he missed 2007 AFC Asian Cup finals due to an injury. His absence was a big blow to the Japan NT.
Tulio went on to score his second goal for the Japanese national team, on 22 August 2007, in an international friendly versus Cameroon – a header. On 17 July 2008, he scored his first hat-trick in J. League Division 1 in a league game against Tokyo Verdy. On 22 December 2009, after falling out with the management at Urawa as he was deployed in an unfamiliar position at the back, Tulio joined Nagoya Grampus. He played 168 games and scored 37 goals for his ex-club.
On 30 May 2010, he scored for Japan against England in the 7th minute of a World Cup warm-up, and also scored for England against Japan in the form of an own goal 67 minutes later. As Japan's captain Yuji Nakazawa later did the same thing, the game finished 2–1 for England.
On 4 June 2010, he scored for Côte d'Ivoire against Japan in the form of an own goal in the 13th minute of a friendly match. Three minutes later, he injured Côte d'Ivoire attacker Didier Drogba's elbow which was fractured by high challenge from Tulio.
He was a playmaker in his younger days, whose passes and headers helped his team score goals.
On 9 January 2016, Nagoya Grampus announced that the club and Tulio are parting ways.