El vídeo musical fue filmado por la directora inglesa Sophie Muller en varias locaciones de Nueva Orleans, Louisiana, el 21 de junio de 2006.