Traces of Sadness
"Traces of Sadness" on Vanilla Ninja teine album. See avaldati 2004. aasta juunis. Album sisaldab singleid "Tough Enough", "Don't Go Too Fast", "Liar" ja "When the Indians Cry". Album jõudis Saksamaal albumite edetabelis kolmandale kohale ning sellele järgnes bändi tuntus ka teistes riikides, näiteks Šveitsis ja Austrias.