At first, ERT organized a National Final that consisted of a Pop Idol style TV show called Eurostar which started on December 5, 2003. 36 people were selected to compete and were divided into three groups of twelve. The contestants of each group had to compete against each other over two heats. The six contestants with the highest score of each group proceeded to the following round. Apostolos Psichramis was the winner of the final and was supposed to move on to a selection process for a song, however, ERT internally selected "Shake It" by Nikos Terzis, sung by Sakis Rouvas after they had finialized a deal with him to sing. The winner and the two finalists from Eurostar were then given the opportunity of performing back-up vocals in Istanbul, Turkey.
As Greece had not finished in the top 10 at the 2003 Contest, the song was first performed in the semi-final. It was performed tenth following Monaco's Märyon with "Notre Planète" and preceding Ukraine's Ruslana with "Wild Dances". At the close of voting, it had received 238 points, placing 3rd in the 22-strong field and qualifying for the final.
Sakis Rouvas performed with two dancers with his back-up vocals to the side. During the performance Sakis ripped off the white suits his dancers were wearing to reveal sparkling tassel attire. The dancers later ripped off Sakis' jacket. At the close of voting, it had received 252 points, placing 3rd in a field of 24. It was succeeded as Greek representative at the 2005 Contest by Elena Paparizou with "My Number One".
Rouvas' entry "Shake It" broke and still maintains a number of records, both for Greece and abroad. With 252 points, "Shake It" is the highest-scoring third place entrant in the history of the Eurovision Song Contest. This record was previously held by Malta's1998 performance by Chiara Siracusa with "The One That I Love" that earned 166 points. Although there were only 25 countries voting in 1998 and 36 in 2004, the Greek point average is higher. The current runner-up is Bosnia and Herzegovina's2006 "Lejla" by Hari Mata Hari with 229 points. Meanwhile, it received 238 points in the semi-final (where it also placed third), becoming the highest-scoring third place in the semi-final as well, and also having the highest point average of a third place for both events.
"Shake It" is by far Greece's most successful entrant in cumulative points. It received 252 points from 35 other countries, making it the highest-scoring Greek entrant to date. While it is arguable that in 2004 and beyond there have been more countries participating than in the past, the song achieved a point average of 7.2, also becoming the highest point average of a Greek entrant, a record that has yet to be broken. Both of these records were previously held by Antique with "(I Would) Die For You" in 2001, having scored 147 from 22 countries and having an average of 6.68.
Rouvas' effort is only the second entrant of Greece that was awarded points by every other country in a single contest, the other year being in 2001 with Antique. However, in 2001, only 23 countries voted, while in 2004, 36 countries voted, making it difficult to compare the two years.
The entry also received five sets of 12 points, the maximum amount of points that can be awarded, which was the highest amount of 12 points Greece had ever received in a single contest, up until that point. However, the record was broken the following year.
Finally, "Shake It" is by far the most successful Greek Eurovision entrant in charts and sales. It peaked at number 1 for an extended amount of weeks in both Greece and Cyprus. It charted for nearly one year on the Greek Singles Chart. The song also topped both countries' airplay charts and entered the top 40 of the Swedish Singles chart. It was certified 4× platinum in Greece and 3× platinum in Cyprus, becoming the best-selling single of the year. The high sales of the record helped earn Rouvas his first World Music Award. It has since become one of the best-selling CD singles of all time in Greece.
Rouvas' enjoyed a boost in his career after returning to Greece. His single "Shake It" had debuted on the Greek Singles Chart at number 2, climbing up to number 1 in its second week, where it remained for eight straight weeks. The single also peaked at number 1 on the Radio Airplay Chart for months at a time. The success helped Rouvas win at the Arion Music Awards in April, 2005 where he won the award for "Highest Greek Single Sales of 2004." The single went platinum in its first week and was certified double platinum by September 2004, finally achieving 4x platinum status in Greece in 2005. Rouvas' ninth studio album To Hrono Stamatao was re-released with "Shake It" and became double platinum, becoming his third multi-platinum album. While in the three years prior to Eurovision he had entered the international music scene, the Eurovision further fueled his success abroad. His English album Ola Kala was re-released in many parts of Europe to contain the Eurovision entrant and newer tracks.
In 2006, Rouvas presented the 2006 contest alongside Greek-American presenter Maria Menounos, while since his performance, he has been approached multiple times to represent Greece once again in the contest, with the artist denying these proposals. On July 15, 2008, however, Rouvas was confirmed as Greece's representative in the Eurovision Song Contest 2009.