[1] Taskoudis finished sixth in the 66-kg class when Greece hosted the 2004 Summer Olympics in Athens, and has also captured three gold medals in the 74-kg division in beach wrestling at the World Championships (2012 to 2014).

Taskoudis qualified for the Greek squad, as a 19-year-old teen, in the men's welterweight class (66 kg), when his nation hosted the world to the 2004 Summer Olympics in Athens.

He filled up an entry by the International Federation of Association Wrestling and the Hellenic Olympic Committee, as Greece received an automatic berth for being the host nation.

[2][4][5] Amassed the home crowd inside Ano Liossia Olympic Hall, Taskoudis opened the prelim pool with a marvelous victory over India's Ramesh Kumar by a 10–8 verdict, before losing his succeeding match 6–12 to Armenia's Zhirayr Hovhannisyan.

He was overpowered by eventual Olympic champion Elbrus Tedeyev of Ukraine in the quarterfinal match 2–6, and then followed it with a 4–6 setback in a playoff against Japan's Kazuhiko Ikematsu for a fifth-place finish, dropping him to sixth.