Album opowiadał historię Króla Artura i Rycerzy Okrągłego Stołu. Zaraz po zakończeniu trylogii grupa ruszyła w trasę koncertową, podczas której dołączył do niej Hans Peter Katzenburg, grający na instrumentach klawiszowych.
Dwudziestolecie W 2000 roku, z okazji dwudziestolecia istnienia zespołu, odbył się koncert na Zeche w Bochum, gdzie zagrane zostały wszystkie najpopularniejsze utwory grupy, jak również te mniej znane. Tuż przed koncertem zespół opuścił Uwe Lulis, tłumacząc się powodami prywatnymi i finansowymi. Założył on później grupę Rebellion. Na jego miejsce został przyjęty były gitarzysta Rage, Manni Schmidt.
Z nowym gitarzystą i nakładem nowej wytwórni (Nuclear Blast), w 2001 roku zespół nagrał album The Grave Digger, inspirowany twórczością Edgara Allana Poe. Rok później został zarejestrowany pierwszy w historii grupy materiał koncertowy, nazwany Tunes of Wacken, nagrany podczas festiwalu Wacken Open Air.
W 2003 roku zespół nagrał kolejny album koncepcyjny, Rheingold, związany z operą Pierścień Nibelunga, Richarda Wagnera.