Historia thumb|left|Od lewej: Warrel Dane, Tim Johnston i Chris Broderick podczas koncertu na festiwalu Summer Breeze w Dinkelsbühl 17 sierpnia 2007 roku Grupa Nevermore powstała w 1991 roku w Seattle w stanie Waszyngton z inicjatywy byłych członków zespołu Sanctuary: wokalisty Warrela Dane’a, basisty Jima Shepparda i gitarzysty Jeffa Loomisa. W 1992 roku nakładem zespołu ukazało się pierwsze wydawnictwo zespołu pt. Utopia. W 1994 roku ukazało się drugie demo pt. 1994 demo. 1 stycznia 1995 roku nakładem Century Media Records ukazał się debiutancki album grupy zatytułowany Nevermore. 28 maja 1996 ukazał się minialbum In Memory. 23 lipca 1996 został wydany drugi album Nevermore pt. The Politics of Ecstasy. 6 stycznia 1999 ukazał się trzeci album formacji pt. Dreaming Neon Black. We wrześniu 2000 roku został wydany czwarty album formacji zatytułowany Dead Heart in a Dead World. Wydawnictwo ukazało się również we wzbogaconej wersji zawierającą teledysk do utworu „Next In Line”. Nagrania odbyły się w studiu Village w El Paso, w stanie Teksas we współpracy z producentem muzycznym Andym Sneapem. W ramach promocji zespół odbył trasę koncertową w Stanach Zjednoczonych wraz z In Flames i Shadows Fall.