Para o segundo álbum, Night of the Stormrider (1992) os vocais e bateria foram trocados por respectivamente John Greely e Richey Secchiari. O vocalista é nitidamente melhor que o do disco anterior e isto foi um fator decisivo para as composições já que a banda necessitava de um vocal forte que conseguisse dar verdadeiros gritos raivosos que iriam caracterizar o feeling da obra. O disco é conceitual com uma história um tanto quanto assustadora. Trata-se de um homem que se sente traído pela religião e se vira contra ela com raiva e ódio. As forças do mal juntam-se a este homem e passam a utilizá-lo para a realização de suas intenções, colocam-no para disseminar a morte e a destruição na Terra. Com tudo isto, ele não sente nenhum remorso e como recompensa alcança a vida eterna, porém, no Inferno. Aparecem no álbum algumas passagens melódicas com teclado, pianos e corais. Porém estes componentes não são assim tão evidentes. A música interage perfeitamente com a história que é contada, nos momentos de alegria, ódio, confusão e tristeza presentes nas letras.
Após três anos sem lançar nenhum trabalho, eis que surge Burnt Offerings (1995), com um novo baterista (Rodney Beasley) e um novo vocalista : Matthew Barlow, que viria a se firmar como uma das grandes vozes do heavy metal atual. Este é o álbum mais pesado do Iced Earth, mas mesmo assim conserva o toque melódico característico da banda. É com este disco que o mundo do heavy metal pôde conhecer a obra prima chamada "Dante's Inferno" que nos leva aos Nove Planos do Inferno em dezesseis minutos, onde cada plano é mais assustador e demoníaco.
O Iced Earth continua a amadurecer a sua música e em 1996 lança The Dark Saga, álbum conceitual baseado na popular história em quadrinhos "Spawn". Conta a história de um homem que vende sua alma em troca de saber quem era seu verdadeiro amor na Terra. Mas com isto ele descobre que ela está casada com seu melhor amigo . Ele então fica completamente sozinho no mundo, e embora fosse um homem bom, estava freqüentemente influenciado pelas forças do mal. Tudo o que ele desejava lhe era negado, até mesmo sua própria morte. Os até então fãs do Iced Earth estranharam um pouco este álbum pela mudança na musicalidade. A finalidade disso segundo a banda era diminuir a técnica e focalizar a atenção na criação das letras. A música é no geral mais simples, melódica e emotiva do que os álbuns anteriores. E isto não quer dizer que as composições são menos interessantes, muito pelo contrário, uma das mais impressionantes composições da banda aparece neste álbum e se chama "Question of Heaven" que mistura peso com suavidade de uma maneira que dificilmente se pode encontrar em outras músicas. Isto sem mencionar a qualidade da letra que emociona a qualquer um.
No ano seguinte foi lançado Days of Purgatory que conta com a participação de vários outros músicos. Este disco contém músicas escritas entre 1986 e 1994. Algumas remixadas e regravadas ficando melhores do que as originais. A idéia da palavra "purgatory" no título veio por alguns motivos. Primeiro porque era o nome inicial da banda entre 84 e 89 e também porque simboliza os muitos anos de sofrimento que a banda passou para chegar até onde chegou.
Após o sucesso de The Dark Saga, todos estavam curiosos para saber qual seria o próximo passo do Iced Earth para crescer na cena heavy metal, e é claro que os fãs não foram desapontados. Muito pelo contrário, o disco que se segue chama-se Something Wicked This Way Comes (1998) e contém muita coisa antiga, muita coisa nova e é claro.. "something wicked". Para as gravações dos solos foi contratado o guitarrista Larry Tarnowski. Muito mais melódico do que os discos anteriores e sem perder o peso característico da banda, este que é o um dos melhores lançamentos do ano de 98, é um tanto quanto melancólico adicionado às passagens acústicas, entre elas a 1776 que mistura metal pesado com flautas criando uma atmosfera muito interessante. O disco ainda possui a trilogia formada por 'Prophecy, 'Birth Of The Wicked' e 'Coming Curse'. Este é tido como um precursor para o próximo álbum, portanto todos devem estar atentos para o que estiver por vir!
Na tour que se seguiu grabaram na Grécia shows que dariam origem ao álbum triplo Alive In Athens. Depois da tour a banda tirou longas férias, tempo suficiente para que Schaffer investisse seus esforços no projeto Demons & Wizards, em parceria com Hansi Kursch, do Blind Guardian.
De volta das férias, Horror Show foi gravado em 2000 e lançado em 2001, álbum temático, versando sobre contos de terror e sendo um dos mais pesados do grupo até então. No novo álbum foram apresentados o baixista Steve Di Giorgio (Death, Testament e Sadus) e o baterista Richard Christy (Control Denied, que havia tocado com Schaffer no Demons & Wizards). No intervalo durante as gravações saiu o aperitivo The Melancholy EP, com uma faixa inédita e covers do Black Sabbath, Judas Priest e Bad Company. DiGiorgia sairia da banda e para seu lugar voltaria James MacDonough.
Em 2003 Matthew Barlow, aparentemente afetado pelos atentados de 11 de setembro de 2002, anunciou que deixaria o grupo para seguir uma carreira longe da música. Apesar de o novo álbum, The Glorious Burden, já estar praticamente pronto, o lançamento foi adiado e todos os vocais regravados pelo novo vocalista, Tim "Ripper" Owens, que havia sido recentemente desligado do Judas Priest para a volta de Rob Halford. O álbum chega às lojas no início de 2004. O tema desta vez era a guerra civil americana pela independência no século 19. Durante a tour que se seguiu foi a vez de Richard Christy deixar a banda, sendo substituido pelo baterista Bobby Jarzombek. Christy pelo que se sabe seguiu carreira como comediante (!).
