Scott Kearnan, de Boston.com, colocó al sencillo en el décimo lugar de los treinta más destacados de la intérprete, y recalcó que «este primer sencillo del álbum "Ray of Light", producido por William Orbit, está lleno de una percusión deslumbrante y exuberantes elementos electrónicos que fueron innovadores hace más de 15 años, pero que también logran que ["Frozen"] suene genial hoy en día».