Christodoulou started his career with Dafni, and he spent most of his career (1983–1997) with Panionios, winning the Greek Cup with them in the year 1991. With Panionios, he played on the same team with his brother Christos Christodoulou. He was mainly a power forward, but his admirable all-around skills allowed him to play all five positions. Many journalist called him the European Charles Barkley. Christodoulou spent the last year of his career playing for Panathinaikos, and winning a Greek Basket League championship with them in the 1997-98 season. One year later, he retired.