W 2005 Vanilla Ninja zostały ogłoszone reprezentantkami Szwajcarii z utworem „Cool Vibes” w 50. Konkursie Piosenki Eurowizji organizowanym w Kijowie. Pewne kontrowersje wokół zespołu wywołał wówczas w mediach temat wieku Triinu Kivilaan, która w momencie zgłoszenia zespołu do konkursu nie miała ukończonych wymaganych regulaminem 16 lat (obchodziła urodziny przed finałem imprezy, w związku z czym oficjalnie żadne zasady nie zostały złamane). 28 lutego tego roku wydany został singel „I Know”, zaś 14 marca trzeci album studyjny grupy, zatytułowany Blue Tattoo. Wydawnictwo uplasowało się w czołowej dziesiątce list przebojów w Niemczech, Austrii i Szwajcarii, z kolei w Polsce dotarło do czołowej dwudziestki OLiS. W kwietniu tego roku wyruszyły w promującą najnowszy album trasę koncertową Blue Tattoo Tour obejmującą koncerty po Europie – w Niemczech, Szwajcarii, Austrii i Luksemburgu. Jeszcze przed rozpoczęciem trasy, w marcu 2005 w jednym z niemieckich programów telewizyjnych ujawniono, że wytwórnia płytowa Davida Brandesa zleciła wykupienie ze sklepów setek egzemplarzy singla „When the Indians Cry” w celu uzyskania wyższej pozycji na listach przebojów.