W tym samym roku perkusista Martin Lopez odszedł od zespołu i dołączył do Opeth. Jego miejsce zajął Fredrik Andersson (wcześniej w A Canorous Quintet). Zespół nagrał kolejne dwa albumy: The Avenger (1999) i The Crusher (2001). W przeciągu dwóch lat dzielących te wydawnictwa Amon Amarth koncertował po Europie dzieląc scenę z takimi grupami jak Marduk, Vader czy Morbid Angel. W 2002 roku wyruszył w trasę po USA. W tym samym roku wydana została czwarta płyta zatytułowana Versus the World. W ramach promocji zespół odbył 3 trasy po Ameryce Północnej i 2 po Europie.
W 2004 roku ukazał się Fate of Norns. Zawierał on jeden z najbardziej rozpoznawalnych utworów grupy: „The Pursuit of Vikings”, do którego powstał też teledysk. Amon Amarth po raz kolejny ruszył w trasę, promując album w Ameryce Północnej i Europie, odwiedzając także nowe miejsca jak Islandia, Polska, Chorwacja, Irlandia. Grał również na Wacken Open Air Festival. Rok później ukazało się pierwsze DVD zespołu Wrath of the Norsemen, zawierające trzy płyty z pełnym zapisem pięciu koncertów. W 2006 roku grupa nagrała kolejny, szósty album studyjny, With Oden on Our Side. W listopadzie tego samego roku wraz z Wintersun i Týr koncertowałą po Europie, zaś w grudniu odbyła trasę po USA wraz z Children of Bodom, Sanctity i Gojira.