Группу Legenda организовал известнейший финский музыкант Sir Luttinen (настоящее имя - Kimmo Luttinen), прославившийся тем, что был основным композитором и исполнителем на трех культовейших альбомах садомазохистов Impaled Nazarene. Еще в находясь в составе Impaled Nazarene, Сир Люттинен замутил небольшой проект под названием Gandharva Legenda, в который помимо него вошли Reima Kellokoski и его подруга.

Впрочем, до некоторого времени Gandharva Legenda была для Сира Люттинена, мягко говоря, "на вторых ролях". Однако все резко изменилось в 1995 году, когда Сир принял решение покинуть ставший для него неинтересным Impaled Nazarene и сосредоточиться на своем детище (злые языки утверждают, что большую роль в развязке сыграла драка между братьями, произошедшая прямо в студии).

Весной 1996 года наш герой рекрутирует басиста по имени Nikko Karppinen (ex-Maple Cross, а также известного тем, что он помогал Sentenced в туре в поддержку альбома "Amok"), и летом записывает демо "Chronicles. Chapter I", которое позволяет друзьям подписаться на Holy Records. Скопировано с Dark-World.ru.

Весной 1997 года проект, потеряв первое слово от названия (то есть переименовавшийся в просто Legenda), засел в известнейшей финской студии Tico-Tico, чтобы записать свой первый альбом, "Autumnal", в итоге появившейся на прилавках в мае. Направление, в котором пошла Legenda было указано еще на третьем диске Impaled Nazarene (достаточно послушать вещь "Blood Is Thicker Than Water"), "блэковый" вокал в сочетании с жесткой, но мелодичной музыкой, короче говоря, сам Сир Люттинен называет это amospheric metal. "Autumnal", записанный всего за пять дней, не прошел незамеченным (и не только потому, что имя Legenda кровно связано с легендарными Impaled Nazarene), получив отличную прессу по всему миру.

Второй релиз, получивший лаконичное название "Eclipse", не заставил себя долго ждать - он появился спустя год, в 1998. Как и дебют, он был отлично принят всеми заинтересованными лицами, показав явный прогресс во всех отношениях.

К сожалению, выпустив два альбома, в 1998 году группа распалась.