Trail of Tears så dagens lys i 1997. Frem til da hadde noen av bandmedlemmene brukt et par år på å eksperimentere under navnet Natt. Etter å ha funnet ut deres musikalske retning, ble navnet endret til Trail of Tears, i begynnelsen av 1997. En 3-spors demotape med tittelen «When Silence Cries…» ble spilt inn kort tid etter i Jailhouse Studio til stor anerkjennelse.

Demoen førte til en rekke kontraktsmessige tilbud fra plateselskaper rundt om i verden, og tidlig i 1998 signerte bandet en avtale om å gi ut to album, med det nederlandske merket DSFA Records.

En rekke turnéer fulgte, inkludert europeiske turneer og show med blant andre Tristania, The Sins of thy Beloved, Cradle of Filth, Biohazard og flere andre band. Det hele ble kronet med en episk opptreden på Dynamo Open Air-festival, i Eindhoven (NL).

Umiddelbart etter begynte bandet arbeidet med oppfølgingsalbumet, og etter å ha brukt siste del av 1999 på å lage sangene, gikk de inn i Jailhouse Studio for å spille inn «Profoundemonium», som ble lisensiert til Napalm Records utenfor Benelux-landene og utgitt i 2000. Bandet fortsatte å holde seg aktive på turnékretsen, og fullførte flere europeiske runder, og på festivaler som Wacken Open Air, Quart Festival, Eurorock og Metal Dayz for å nevne noen.

Sommeren 2001 signerer bandet en avtale på tre album med Østerrikes Napalm Records, og går inn i Soundsuite Studio i Marseille (FR), med produsent Terje Refsnes i februar 2002. En veldig travel turnéplan starter, inkludert hele turneer og mange show i Europa, samt den første hele meksikanske turneen i juni 2003.

Etter å ha brukt over et år på låtskrivingsprosessen for det fjerde albumet, valgte bandet en tyngre og mer ekstrem tilnærming som tydelig kan høres på «Free Fall into Fear», som utgis i februar 2005 av Napalm Records. Albumet ble spilt inn hos Endre Kirkesola i Dub Studio i Kristiansand, og for å promotere albumet gjennomførte bandet en meget vellykket turné med Therion og Tristania, som tok bandet til 14 europeiske land. Bandet er også tilbake på festivaler igjen, og spiller blant annet Tysklands Summer Breeze-festival.

Det tok ikke lang tid før bandet gjenopptok arbeidet med låtskrivingen, og nesten 12 måneder ble brukt på å lage det som skulle bli det mest modne og eventyrlige albumet til dags dato, «Existentia». Albumet tok Trail of Tears igjen tilbake til Soundsuite Studio med produsent Terje Refsnes sommeren 2006. Albumet inneholder gjestespill av den norske keyboardtrollmannen Bernt Moen og den fantastiske franske sangeren Emmanuelle Zoldan.

«Existentia» blir utgitt av Napalm Records i januar 2007 til mye anerkjennelse og overveldende anmeldelser. Bandet følger opp med ytterligere turnéer, viktigst av alt med deres første nordamerikanske turné noensinne, og spiller nesten 30 show over hele USA så vel som Canada. Sommeren 2008 spiller i tillegg bandet også flere festivaler enn noen gang før, inkludert Wave Gothik Treffen og Metal Mania Open Air.

Ytterligere to albumutgivelser følger i form av Bloodstained Endurance (2009), og Oscillation (2013) før bandet settes på pause i 2013

Spol syv år fremover, og Trail of Tears kunngjør at de kommer tilbake til scenen i 2020. Med en fornyet line-up med originalmedlemmene Ronny Thorsen, Runar Hansen og Jonathan Alejandro Perez, slår bandet seg sammen med det mangeårige medlemmet Endre Moe, og rekrutterer nye gitarist Nicolay «Jørni» Johnsen, samt den anerkjente spanske sangeren Ailyn. Bandet er igjen klare for å returnere til live-kretsen, med en rekke planer for både liveopptredener, så vel som nye musikalske innspillinger.