Latem 2000 roku zespół wyruszył w kolejną trasę, dając koncerty w Niemczech, Austrii, Szwajcarii, Holandii, Belgii, Włoszech, Grecji oraz Hiszpanii. Jej owocem był pierwszy album live (The Expedition). Parę miesięcy później grupa zaprezentowała swój piąty album, Karma. Szósty album zatytułowany Epica został wydany w 2003 roku. Zarówno ten album jak i kolejny (The Black Halo wydany w 2005 roku) bazują na dramacie Johanna Wolfganga von Goethego o tytule Faust, opowiadającym o człowieku, który zaprzedał swoją duszę diabłu. Podczas trasy Black Halo World Tour headlinerami dla zespołu były grupy Epica, Kotipelto oraz Silent Force.
W 2005 roku Kamelot nagrał swoje pierwsze teledyski do utworów „The Haunting (Somewhere in Time)” oraz „March of Mephisto” pochodzących z albumu The Black Halo. Oba teledyski reżyserował Patric Ullaeus. 5 października 2005 roku do zespołu dołączył piąty oficjalny członek, Oliver Palotai (instrumenty klawiszowe oraz okazyjnie gitara).
W drugiej połowie trasy Black Halo World Tour zespół odwiedził takie kraje jak USA, Kanada, Brazylia, Holandia, Belgia, Szwecja oraz Norwegia.