A dal videoklipjétvideóklipjét [[Los Angeles]]ben rögzítették, Williams mint egy transzvesztita tűnik fel felékszerezve, egy nightklubban szerepel transzvesztiták előtt. Több híres transzvesztita is szerepel a klipben (Alexis Arquette, Chi Chi LaRue).<ref name="thesun">{{cite news|url=http://www.thesun.co.uk/article/0,,4-2007020439,00.html|title=Robbie's frocky horror show|publisher=[[The Sun (newspaper)|The Sun]]|first=Victoria|last=Newton|authorlink=Victoria Newton}}</ref> A videoklipetvideóklipet Johan Renck rendezte, aki [[Madonna (énekesnő)|Madonna]] két korábbi videojának, a ''[[Nothing Really Matters]]''-nek (1999) és a ''[[Hung Up]]''-nak (2005) volt a rendezője.