Kitaristi Jon Schaffer perusti yhtyeen Indianassa vuonna 1984 nimellä Purgatory. Floridaan muuton ja nimenvaihdon jälkeen heidän vuonna 1988 tekemänsä demo Enter the Realm herätti Century Media -levy-yhtiön kiinnostuksen ja heidän kauttaan julkaistiin yhtyeen nimeä kantanut debyyttialbumi vuonna 1991. Seuraavana vuonna ilmestynyttä Night of the Stormrider -albumia seurasi kolmen vuoden tauko. Iced Earth palasi vuonna 1995 albumillaan Burnt Offerings, jolloin mikrofonin varteen John Greelyn tilalle oli pestattu Matt Barlow, joka saavutti heti kuulijoiden varauksettoman suosion. Seuraavana vuonna ilmestynyt The Dark Saga oli Spawn-sarjakuvan ympärille kasattu teema-albumi.
Syyskuussa 2007 Iced Earth julkaisi albumin Framing Armageddon. Se on Something Wicked This Way Comes -albumiin perustuvien teema-albumeiden ensimmäinen osa, toinen osa The Crucible of Man ilmestyi vuonna 2008.
5. joulukuuta 2007 Schaffer ilmoitti yhtyeen sivustolla Barlow’n palaavan takaisin Iced Earthiin. Schaffer oli keskustellut kiertueella useiden yhtyeen kuulijoiden kanssa ja useimmiten ilmeni, että Barlow’ta kaivattiin takaisin. Schaffer sai myös tietää, että Barlow oli palannut metallimusiikin pariin Pyramaze-yhtyeen laulajana ja näin ollen otti häneen yhteyttä kysyäkseen, mitä mieltä hän olisi myös Iced Earthiin paluusta. Barlow näin ollen lauloi 2008 ilmestyneen Something Wicked -saagan toisella osalla. Matt Barlow lähti kuitenkin yhtyeestä toistamiseen 2011, ja hänen tilalleen tuli Stu Block, joka myös laulaa Iced Earthin seuraavana vuonna julkaistulla studiolevyllä Dystopia. Albumin julkaisun jälkeen yhtye suoritti maailmankiertueen, jolla nauhoitettiin myös livealbumi Live in Ancient Kourion.
Yhtye alkoi työstää seuraavaa studioalbumiaan vuonna 2013, ja 2014 julkaistiin Plagues of Babylon.
Yhtyeen jäsen Jon Schaffer oli yksi niistä mielenosoittajista, jotka tunkeutuivat kongressiinWashingtonissa 6. tammikuuta 2021 ja hänet pidätettiin hieman myöhemmin. Helmikuussa 2021 laulusolisti Stu Block ja basisti Luke Appleton erosivat yhtyeestä.[1]