Pod koniec 2001 roku zespół opuścił gitarzysta Curran Murphy, który dołączył do Annihilator. 29 lipca 2003 roku ukazał się szósty album grupy pt. Enemies of Reality. Płyta została zarejestrowana w rodzinnym mieście zespołu Seattle we współpracy z producentem muzycznym Kelly Grayem, który wcześniej poprzednio m.in. z Dokken i Queensrÿche. We wrześniu i październiku odbyło się europejskie tournée. Koncerty Nevermore poprzedziła szwedzka grupą death metalowa Arch Enemy. W kwietniu 2004 roku do zespołu dołączył gitarzysta Steve Smyth. Muzyk, który występował poprzednio w formacji Testament. thumb|Jeff Loomis podczas koncertu na festiwalu Summer Breeze w Dinkelsbühl 17 sierpnia 2007 roku 26 lipca 2005 roku ukazał się siódmy album grupy pt. This Godless Endeavor. Utwory z przeznaczeniem na płytę zostały zarejestrowane w Backstage Studios we współpracy z producentem muzycznym Andym Sneapem. Okładkę wydawnictwa przygotował Hugh Syme, który współpracował poprzednio z zespołami autora Rush i Megadeth. W ramach promocji wydawnictwa został zrealizowane teledyski do utworów „Final Product” i „Born”. We wrześniu Nervemore odbyło trasę koncertową w Europie. Koncerty zespołu poprzedziły grupy Mercenary i Dew-Scented. W 2006 roku Chris Broderick zastąpił borykającego się z problemami zdrowotnymi Steve’a Smytha. Broderick wziął udział m.in.