Перед записью дебютного альбома Legendary Tales в 1997 году, Rhapsody покинул вокалист. Новым фронтменом стал Фабио Лионе, ранее певший в группе Labyrinth. Фабио не был прежде знаком с Лукой Турилли и Алексом Старополи, поэтому отношения между ними начались со скандала: вокалист отказывался исполнять не понравившуюся ему песню Land of Immortals. Однако вскоре отношения в группе наладились, и Лионе стал постоянным вокалистом Rhapsody на всех альбомах группы.

Дебютный альбом стал началом многосерийной фэнтези-саги «Хроники Алгалорда», написанной Турилли, который является основным автором текстов группы. Альбом был выдержан в стиле мелодичного пауэр-метала, с использованием некоторых элементов фолк-музыки и музыки барокко. На следующий год группа выпустила второй альбом Symphony of Enchanted Lands, сюжетно и стилистически продолжающий первый. В записи альбома принял участие хор донских казаков.

Изменения состава

С 1999 года Турилли начал выпускать сольные альбомы, не прекращая усиленно работать с Rhapsody. В 1999 году группу покинул ударник Карбонера, которого сменил сессионный барабанщик Алекс Хольцварт (брат сессионного басиста Blind Guardian Оливера Хольцварта), официально включенный в состав группы только в 2003 году. На следующих альбомах, Dawn of Victory и Rain of a Thousand Flames группа продолжала сюжетную сагу о стране Алгалорд, Воине Льда и Изумрудном Мече. Звучание песен группы при этом заметно «потяжелело», особенно это заметно в альбоме Power of the DragonFlame. Турилли даже упоминал о желании записать альбом в стиле симфо-блэк-метал, но из-за разногласий со студией этот проект не был осуществлен.

До 2000 года Rhapsody почти не выступали вживую. Музыканты не были уверены в возможности полноценного переноса на сцену всех элементов их музыки из-за большого количества инструментов и сложных аранжировок. Но в 2000 году группа впервые отправилась в полноценный европейский тур со Stratovarius и Sonata Arctica. Вскоре после тура группу оставил басист Алессандро Лотта, закончивший музыкальную карьеру ради семьи. На альбоме Power of the DragonFlame партии баса исполнены самим Турилли, для живых же выступлений был приглашён француз Патрис Гуирс. С его участием прошёл первый южноамериканский тур Rhapsody.

Известность группы распространилась далеко за пределы Италии и даже Европы, и группа вскоре ушла с маленького лейбла Limb music. Последним их релизом с этой компанией стал сборник хитов Tales from the Emerald Sword Saga. Новый альбом 2004 года Symphony of Enchanted Lands II: the Dark Secret вышел на SPV Steamhammer. На нём Rhapsody пригласили известного голливудского актёра Кристофера Ли (Саруман, граф Дуку) в качестве со-сценариста альбома и для чтения сопроводительного текста «от рассказчика». Кристофер Ли также спел дуэтом с Фабио балладу the Magic of the Wizard’s Dream, и снялся в двух клипах группы. Сотрудничество между группой и актёром продолжается до сих пор, в том числе совместные выступления вживую.

Новое название

Музыканты Rhapsody близко знакомы с музыкантами американской хэви-метал-группы Manowar, и их музыка оказывала влияние друг на друга. Группы неоднократно проводили совместные туры под общим названием «Demons, Dragons and Warriors», где их третьим партнером была группа HolyHell. Запись концерта в Канаде в рамках этого тура вышла на DVD Live in Canada 2005: The Dark Secret. В 2006 году Rhapsody подписали контракт с лейблом Magic Circle Music, принадлежащим Джои Де Майо, лидеру Manowar, американскому итальянцу по происхождению, который лично стал продюсером группы.