Mother Earth címmel jelent meg az ezredforduló környékén a Within Temptation második lemeze, ami azonnal meghozta számukra a nagyobb elismerést. Sharon den Adeléknek azonban elég volt egyetlen dal, ami üstökösként robbantotta számukra a hírnevet, ez pedig az Ice Queen volt.
A lemezen számos, mai napig közkedvelt tétel kapott helyet, ám kétség sem fér ahhoz, hogy az Ice Queen alap követelmény a fanok részéről. A kezdetekben azonban nehéz volt kezelni a hirtelen jött nemzetközi elismerést, Sharon den Adel ezt úgy jellemezte, hogy olyan érzés kerítette őket hatalmába, mintha belecsöppentek volna egy hatalmas hullámba, ami egyre csak terebélyesedett felettük.
„Ez volt az első alkalom, amikor realizálódott bennünk, hogy most valami nagyon különleges dolog történik velünk – legalábbis mi így éreztük.” – emlékezett vissza Sharon den Adel.
A nóta olyannyira nagy sikert aratott, hogy a banda azonnal meghívást kapott a legnagyobb fesztiválokra, a koncertjeikre pedig sorra fogytak a jegyek.
„Le voltunk nyűgözve. Szerintem, az embereknek bejönnek a súlyosabb részek, hiszen egyszerre vannak benne romantikus és egyben titokzatos részek.” – osztotta meg gondolatát Robert Westerholt.
„Valójában ez egy érzelmes dal a természetről, a jégkirálynő pedig az eljövendő tél metaforája." – meséli tovább Sharon. „Valójában, ez ténylegesen egy karácsonyi dal" – tette hozzá Robert Westerholt.
