Koukodimos was born in Melbourne, Australia on September 14, 1969. His parents hailed from Agios Dimitrios, Pieria prefecture. He was an athlete of GAS Archelaus Katerini and later of PAOK and Iraklis.
Koukodimos broke the Greek record for the long jump four times, the last time being on June 5, 1994 in Chania, Crete with a 8.36m performance. In indoors competition, he broke the Greek record seven times and was the first Greek athlete to break the 8m mark on March 13, 1994 (8.09m).
Among his many honours, Koukodimos has a silver medal in the European Games of 1994, two golds in the Mediterranean Games and nine gold medals in the Balkan Games. He was voted Greek athlete of the year in 1995.
Following his career as an athlete, Koukodimos was appointed Secretary General of Sports in April 2004. In March 2006, he resigned to seek public office as an MP for Pieria. He was duly elected in 2007 under the banner of New Democracy.
Koukodimos is married with three children.