Celestial a été fondé en 1998 par le batteur Jere Luokkamäki et le bassiste Ari Katajamäki. Ils sont rejoints en 1999 par le guitariste Tapani Kangas et entrent en studio pour enregistrer une démo qui ne paraîtra finalement jamais. L’année 2000 fut remplie de bouleversement pour le groupe avec le départ de Tapani et Ari qui durent aller faire leur service militaire. La même année, le groupe changea de nom pour devenir Celesty ; le guitariste Juha-Pekka Alanen le rejoignit accompagné d’un ami à lui, le chanteur Kimmo Perämäki. Ils enregistrent leur première démo Warrior of Ice. En 2001, Jere découvre le claviériste Juha Mäenpää, le groupe commence à trouver ses marques.