After the release of "Take Me Home" in August 2001, Sophie Ellis-Bextor released her best-selling single to date in December 2001, "Murder on the Dancefloor." The song peaked at #2 on the UK Singles Chart, stayed on the charts for 23 weeks, and became the most played song of 2002 in all of Europe. The song was such a hit that the singer's label cancelled what was planned to be the next single, "Lover," and replaced it with "Get Over You."
The music video (which was directed by Sophie Muller) takes place at a dance contest whose winners are to gain a pair of golden shoes and a cash prize. Desperate to win, Sophie manages to sneakily injure and disqualify many of the other dancers, poison one judge and seduce another into declaring her the winner which displeases the other dancers.