"Choose Love" fue publicado el 7 de junio de 2005 en los Estados Unidos y un mes más tarde, el 25 de julio, en el Reino Unido.