Группа была образована в Сиэтле в 1994 году после распада группы Sanctuary[2], где играли несколько её участников. В первый состав «Nevermore» вошли вокалист Уоррел Дэйн, басист Джим Шеппард, гитарист Джефф Лумис и барабанщик Ван Вильямс. Подписав контракт с «Century Media», группа начала также своё длительное сотрудничество с продюсером Нилом Керноном, имевшим значительный опыт работы с такими командами как Dokken, Judas Priest и Queensryche.
Выпустив в 1995-м одноимённый альбом, Nevermore отправились сопровождать Death в американском туре и Blind Guardian — в европейском. Вскоре в коллективе появился ещё один гитарист — Пэт О’Брайен из «Monstrosity», дебютировавший на EP 1996 года «In memory».
Релиз, представлявший собой несколько каверов и переработанный материал Sanctuary, получил положительные отзывы со стороны и слушателей, и критиков. В том же году группа издает полноформатный альбом «Politics of Ecstasy». На нем наиболее полно проявились талант О’Брайена, Лумиса и Вильямса. Однако Пэт недолго пробыл в коллективе и ушёл в Cannibal Corpse. На его место был приглашен давний друг «Nevermore» и бывший участник Forbidden Тим Калверт. Тим, помимо исполнения гитарных партий, внёс свой вклад в написание песен. Его композиторский дар вполне проявился на концептуальном альбоме 1999 года «Dreaming Neon Black». Пластинка была посвящена погружению человека в безумие с последующим самоубийством после таинственной смерти его любимой женщины. Диск получил положительные отзывы от прессы: ряд изданий назвали «Dreaming…» альбомом года. За ним последовали напряжённые гастроли с Mercyful Fate по США и с Iced Earth по Европе. В заключение тура группа посетила Австралию.
Частые переезды и бесконечные концерты вывели из равновесия Тима Калверта, и он был вынужден покинуть группу. Оставшись вчетвером, Nevermore наняли нового продюсера, Энди Снипа (Machine Head, Testament, Kreator) и отправились готовить очередной альбом в техасскую студию «Village studios». Новый релиз, «Dead Heart In A Dead World» оказался в списках некоторых рок-изданий среди претендентов на звание лучшего альбома. В поддержку альбома группа отправляется в европейский тур, в рамках которого Nevermore посетили Wacken Open Air, Dynamo, With Full Force.
Последующие два года Nevermore проводят на гастролях, разделяя концертные площадки с такими коллективами как Arch Enemy, In Flames, Shadows Fall, Opeth, Angel Dust, Savatage. К студийной работе группа вернулась в 2003-м, записав с продюсером Келли Грэем (Queensryche, Dokken) очередной альбом, «Enemies Of Reality».