"Suledėjusios žemės" istorija prasidėjo 1984 metais Indianoje, kuomet susibūrė paauglių grupė "Purgatory". Jos idėjinis lyderis - gitaristas Jon Schaffer, o grupėje kartu grojo vokalistas Gene Adam, gitaristas Bill Owen, bosistas Dave Abell ir būgnininkas Greg Seymour. Poros metų bėgyje pasikeitė bosistai - nauju nariu tapo Richard Bateman, o nuo 1988 metų grupėje greta Jon grojo naujas gitaristas Randall Shawver.
"Puragtory" išleido porą demo įrašų - "Burning Oasis" ir "Psychotic Dreams", kur keletas kūrinių vėliau tapo gerai žinomų "Iced Earth" dainų pamatais. Vėliau muzikantai išsiaiškino, kad "Purgatory" vardu jau groja grupė Klyvlende, tad buvo nutarta pakeisti kolektyvo pavadinimą į "Iced Earth".

1989 metais buvo įrašytas demo "Enter the Realm", o taip pat grupė sudalyvavo rinkinio "Metal Mercenaries" įrašuose, kurį prodiusavo buvęs "Savatage" bosistas Keith Collins. O pilno debiutinio albumo reikėjo palaukti iki 1990 metų. Diskas, pavadintas "Iced Earth", gimtinėje pasirodė 3 mėnesiais vėliau nei Europoje, tačiau prieš prasidedant pristatančiajam turui, įvyko rokiruotės grupės gretose. Jei visi gyrė puikų gitaristų Jon Schaffer ir Randall Shawver tandemą, tai vokalistui G.Adam teko atlaikyti kritikos bangą. Jis buvo pakeistas Mike McGill, tačiau pasibaigus turui ir su juo buvo atsisveikinta.
1991 metais prie mikrofono stojo John Greely ir su juo buvo išleistas antrasis diskas "Night of the Stormrider". Albumas JAV vėlgi buvo išleistas tik 1992-aisiais. Tokios "Iced Earth", kurią esame įpratę girdėti, pamatai buvo sudėti tik 1995 metais. Grupėje vėl nauji veidai - vokalistas Matt Barlow ir būgnininkas Rodney Beasley. Šios sudėties grupė išleido diską "Burnt Offerings", kurį pristatant Europoje, teko scena dalintis su "Running Wild", "Gamma Ray", "Grave Digger" ar "Rage".
Didesnės sėkmės buvo sulaukta po 1996 m. albumo "The Dark Saga" išleidimo, kuris buvo paremtas "Spawn" komikso temomis. Vėlgi neapsieita be narių kaitos - į "Iced Earth" atėjo būgnininkas Mark Prator, o gitaristą Abell pakeitė Keith Menser. Vėliau antram gyvenimui buvo prikelti demo "Enter The Realm" įrašai ir pirmų dviejų diskų įrašai. Naujai perrašytos dainos buvo išleistos 1997 metais po "Days of Purgatory" pavadinimu.
Po metų sekė puikus pasirodymas festivalyje "Wacken Open Air" Vokietijoje ir dar vieno sėkmingo albumo "Something Wicked This Way Comes" išleidimas. Iš grupės "Nuclear Assault" atėjo naujasis bosistas James MacDonough, o gitaristą Randall Shawver pakeitė 19-metis virtuozas Larry Tarnowski.
1999 metais buvo išleistas EP "Melancholy", kuriame be jau girdėtų kūrinių buvo įrašyti "Bad Company" ir "Black Sabbath" dainų perdirbiniai. Taip pat buvo surengtas įspūdingi pasirodymai Atėnuose, kur "Iced Earth" pasirodymus matė 120 tūkst. žiūrovų. Iš koncertinės medžiagos buvo sulipdytas trigumas diskas "Alive in Athens".
Naujasis amžius pradėtas daugybe koncertų, o 2001 metais buvo išleistas albumas "Horror Show", kuriame visos dainos buvo skirtos gerai žinomiems siaubo filmų herojams. Toliau buvo numatytas bendras turas su "Judas Priest", tačiau visas kortas sumaišė rugsėjo 11 dienos teroristiniai išpuoliai. Turas buvo atšauktas, tačiau visi įrašai buvo perleisti "Dark Genesis" vardu, kuriame buvo ir papildomas diskas "Tribute To the Gods". Jame grupė perdainavo "Iced Earth" didelę įtaką padariusiu grupių dainas ("Kiss", Alice Cooper, "AC/DC", "Iron Maiden" ir t.t.). Be to, prie grupės prisijungė naujasis būgnininkas Richard Christy.
2002 metai buvo skirti koncertams - surengtas turas Europoje, grota vienoje scenoje su "In Flames" ir "Jag Panzer". Jau buvo paskelbtas sekančio albumo pavadinimas - "The Glorious Burden", tačiau 2003 metų birželį "Iced Earth" gerbėjus pasiekė šokiruojanti žinia - grupės vokalistas Matt Barlow nutarė pasitraukti iš muzikinio pasaulio. Bet netikėtai atsilaisvino įspūdingų vokalinių sugebėjimų dainininkas Tim "Ripper" Owens, kuris turėjo palikti "Judas Priest", kuomet į ją sugrįžo pats Rob Halford. Tokios sudėties kolektyvas naują albumą pateikė gerbėjams 2004 metų  pradžioje. Ilgai lauktas albumas buvo sutiktas gan palankiai, Europoje buvo koncertuota su "Primal Fear", "Thunderstone" ir "Children of Bodom". Nuotaiką kiek sugadino J.Schaffer sveikatos problemos - muzikantui buvo operuota ranka.
Vėliau koncertai persikėlė į gimtinę - scena dalintasi su "Slayer" ir "Halford". Buvo numatyti pasirodymai Japonijoje, tačiau dėl būgnininko Richard Christy išėjimo iš grupės, planus teko atidėti. 2004 metų rugpjūtį išleidžiamas rinktinis albumas "The Blessed and the Damned", o bosistas J.McDonough pakviečiamas į atgimusius "Megadeth". Pastarąjį pakeičia Steve DiGiorgio, dalyvavęs "Horror Show" įrašuose, o būgnininku tampa Bobby Jarzombek, išgarsėjęs kaip solinės buvusio "Skid Row" frontmeno Sebastian Bach grupės narys.
2005 m. Jon Schaffer pareiškia, jog bus sekantys du diskai bus paskutinių trijų albumo "Something Wicked This Way Comes" dainų tęsinys, kurį pristatė puikus EP "Overture of the Wicked". Su nauju gitaristu Troy Seele įrašytas pilnas albumas "Framing Armageddon" pasirodė tik 2007 metais ir jį nustelbė netikėta žinia - į grupės frontmeno vietą sugrįžta Matt Barlow. Grupė nutaria mažinti apsukas ir dalyvauti tik dideliuose festivaliuose bei rengti trumpus turus.
2008 metų rudenį išleidžiamas ilgai lauktas naujas albumas "The Crucible of Man", kuris gal ir neprilygsta geriausiems darbams, įrašytiems su M.Barlow, tačiau grupė vis tiek išlaikė aukštas pozicijas.
2011 metų kovą grupė pranešė liūdną žinią - vėl "Iced Earth" palieka Matt Barlow. Netrukus randama ir pamaina - grupės "Into Eternity" frontmenas Stu Block. Naujasis vokalistas jau dalyvauja disko "Dystopia" įrašuose, o koncertiniame ture "Iced Earth" kaip vieną iš stotelių pasirenka ir Lietuvą.