Late 1990s

Naoya participated at the 1996 Olympics in Atlanta. The Japanese team finished 10th in the team final. Individually, Naoya qualified into the all-around final and finished 12th in the final.

Although Naoya did not get any medal in the 1996 Olympics, he had been quite successful after that. In the 1997 World Championships, he won two bronze medals in the all-around and on parallel bars. In the 1999 World Championships, he had pushed himself to a higher level of success, winning silver medals in all-around and on parallel bars.

2000 Summer Olympics

Following his successes at the World Championships, Naoya eventually came to his second Olympic Games, the 2000 Olympics in Sydney. This time the Japanese gymnastics team was edged by the Russian team for a bronze medal. Individually, Naoya qualified 6th and 10th into the horizontal bar and all-around final respectively. He finally finished 18th in all-around final, and a fall in the horizontal bar final made him come last, with a score of 8.825.

2001–2003

After the 2000 Summer Olympics, Naoya could not regain his form of 2000. In addition, there were some fabulous gymnasts rose in Japan, including Hiroyuki Tomita, Isao Yoneda and Takehiro Kashima. Naoya's character in the national team changed from an all-around competitor into an anchor for the Japanese gymnastics team.

In the 2003 World Championships, Naoya made it into the all-around and parallel bars finals, finishing 7th in the all-around while his teammate, Hiroyuki Tomita, won a bronze in that event. Individually, Naoya placed 4th on his strongest event, parallel bars with a score of 9.675.

2004 Summer Olympics

Naoya made the 2004 Summer Olympics held in Athens, Greece. The Japanese team showed strong performances and eventually won the team gold medal. Naoya placed 4th on floor exercise in prelim with a 9.725, the same score of his teammates, Isao Yoneda and Daisuke Nakano. However, the tie-breaker policy favoured his two teammates into the final. He did not qualify into the all-around final.

After the 2004 Summer Olympics

Naoya was 27 when the Olympics in Athens wrapped, which was an age considered 'old' for gymnastics. Nevertheless, he kept competing. He won a bronze medal with the team in the 2006 World Championships but could not make the 2008 Summer Olympics. He was still competing as of Summer 2010.

Competing For Australia

In 2009, he moved to Australia, competing and winning at the 2009, 2010, 2011, and 2013 Australian National Gymnastics Championships, and winning 2nd place behind Joshua Jefferis in 2012.^[3] In 2012, he gained Australian citizenship, allowing him to compete representing Australia in international competitions.^[4] However, the process was not completed in time for qualification to the 2012 Olympic Games. In 2013, he competed at the 2013 World Championships, narrowly missing the all-around finals, but premiering two new variations of the V-cross on still rings. FIG later announced the Li Ning 2 to V-cross as the "Tsukahara," named after the athlete.^[5] This rare honor for a gymnast is one his father also experienced multiple times. He also competed in the 2014 Commonwealth Games in Glasgow, UK.

In March 2016, Tsukahara retired.^[6]