No ganó en ninguna de las categoría a las que estuvo nominada en los VMAs, pero el sencillo todavía ganó en numerosas entregas de premios, incluyendo un "Teen Choice Award" por Mejor Single y un "MTV Europe Music Award" por Mejor Canción, el éxito de este sencillo no solo estuvo limitado a los Estados Unidos sino que también fue un éxito a nivel internacional.