В 1994 году в норвежском городе Кристиансан образовалась группа "Natt" ("Ночь"), в состав которой вошли вокалист Ронни Турсен, гитаристы Микаль С. Круминс и Тарье Хайсельдол, басист Селль Рюн Хоген и барабанщик Видар Улеберьг. Традиционно все начиналось с каверов, но потом в ход пошли и собственные вещи, а в целом коллектив играл прямолинейный агрессивный металл. С появлением в штате обладательницы сопрано Алес Вик стиль стал дрейфовать к более атмосферному, а после записи одного демо грянули кардинальные перемены. К 1997 году большинство членов команды решило отказаться от ранних трэш/дэт/блэк-влияний и перейти к более симфоничному готик-металлу. И если чистый голос Вик использовался как редкое украшение, то теперь потребовался сильный академический вокал, способный в полной мере противостоять утробному порыкиванию Ронни. Поиски необходимой замены привели к Хелене Микаэльсен, но вот вместе с Алес ушел и симпатизировавший ей Видар. В итоге место за установкой занял проживавший в Норвегии чилиец Джонатан Перес, а кроме того, в составе появился клавишник Франк-Руалд Хоген.
Довершило трансформацию переименование проекта в "Trail Of Tears", и в том же 1997 году уже под новым именем было записано демо "When Silence Cries". И хотя пленка произвела впечатление на издателей, и группе стали поступать различные предложения, Круминс, который не особо поддерживал готическое направление и к тому же поступил в консерваторию, в скором времени ретировался. Его уход, впрочем, прошел довольно мирно, а на месте Микаля материализовался Рюнар Хансен. Быстренько порешав кадровый вопрос, "Trail Of Tears" заключили двухальбомную сделку с нидерландской фирмой "DSFA Records" и осенью 1998-го дебютировали с полнометражкой "Disclosure In Red". Работа была выполнена в модном тогда ключе "красавица и чудовище", а ее мрачный готический романтизм разбавляло влияние агрессивного симфо-блэка.
В поддержку релиза группа гастролировала по Европе с "Tristania" и "Sins Of The Beloved", а ее главное выступление состоялось в 1999-м на фестивале "Dynamo Open Air". В мае 2000-го вышел альбом "Profoundemonium", выдуманное латинское название которого по словам Турсена описывало состояние души, когда человек, находясь в плену собственных мыслей, теряет контроль и не может рассуждать логически. У ряда обозревателей данная работа вызвала стойкие ассоциации с "Tristania", а кроме того, отмечался перекос в сторону мужского гроула. Последний момент, видимо, вызвал недовольство Микаэльсен, и она, воспользовавшись предложением ушедшего из "After Forever" Марка Янсена, присоединилась к его новому проекту "Sahara Dust". Заменой Хелене стала Катрина Паульсен, а параллельно "Trail Of Tears" обновили контракт, перебравшись на "Napalm Records". На альбоме A "New Dimension Of Might" заметно повысился уровень тяжести, а пение стало более разнообразным, поскольку к гроулу и оперному сопрано добавился чистый мужской вокал. Начав промоушен с европейских гастролей, команда переместилась за океан и нанесла визит в Мексику, но по возвращении домой из-за творческих разногласий ушла Паульсен.
Видимо, подустав от женских капризов, "Trail Of Tears" временно отошли от генерального курса, и в 2003 году место у второго микрофона занял обладатель чистого баритона Сьетиль Норьюс из "Green Carnation". Саунд в итоге еще больше огрубел и потяжелел, что и было продемонстрировано альбомом "Free Fall Into Fear", где традиционный готик-металл всерьез потеснили влияния блэк-дэта. Публика приняла эти изменения на позитиве, да и европейские гастроли с "Therion" и "Tristania" прошли вполне успешно, однако в коллективе потихоньку нарастали проблемы. Менеджмент, за который отвечал Турсен, не являлся сильной стороной группы, и это приводило не только к организационным проколам, но и к финансовым трудностям, и в итоге еще до начала очередных сессий ушли Хайсельдол и Хоген.
Несмотря на сокращение состава, в 2006-м группа все же записала полнометражку "Existentia", воспользовавшись услугами парочки гостей, клавишника Бернта Муэна и вокалистки-француженки Эммануэль Зольдан. На пятом альбоме с появлением женского вокала и снижением риффового напора наметился возврат к корням, однако еще до релиза разразился творческий кризис, и все музыканты дружно оставили Ронни в одиночестве, объявив о распаде команды. Тем не менее права на торговую марку "Trail Of Tears" оставались за Турсеном, и он, проигнорировав действия бывших коллег, собрал новую версию группы, в которую помимо вернувшейся Паульсен вошли Бьорн Эрик Нэсс (гитара), Пол Ульсен (гитара), Эндре Муэ (бас) и Като Йенсен (ударные). В 2009 году данная конфигурация выпустила альбом "Bloodstained Endurance", на котором при ослаблении блэкушных влияний произошло возвращение к формуле "красавица и чудовище". Летом 2010-го Ульсен, который также был занят в проекте "Guardians Of Time", счел невозможным для себя работать на два фронта, и таким образом состав сократился до квинтета. Спустя пару лет по личным причинам подал в отставку и Йенсен, и хотя ему нашлась официальная замена в лице Бьорна Дугстада Ронноу, в записи диска "Oscillation" новый барабанщик не участвовал, а партии ударных исполнил Нэсс.
Альбом с его повышенным симфонизмом ознаменовал отход к традиционному готик-металлу, но вот в процессе подготовки обострились внутренние отношения. Катрина стала теснить в лидерстве Ронни, и их конфликты привели к тому, что в январе 2013-го Турсен ушел вместе Муэ и Ронноу. Паульсен же осталась вместе с поддерживавшим ее Нэссом, однако у этой парочки не получилось оживить "Trail Of Tears", и группа окончательно распалась. Ронни занялся возрождением команды лишь по прошествии семи лет, причем наряду со старичками Хансеном, Пересом и Муэ в обновленную версию вошли гитарист Николай Йонсен и вокалистка из Испании Айлин. И хотя по окончании пандемии концерты возобновились, на них исполнялся старый материал, а вот свежачок появился только в 2024-м, да и то в виде EP "Winds Of Disdain".