Pierwszy sukces dziewczyny odniosły podczas krajowych eliminacji do Konkursu Piosenki Eurowizji. Ze swoją piosenką Club Kung Fu zajęły 9 miejsce, jednakże w głosowaniu telewidzów zajęły pierwsze. Wtedy Estończycy oszaleli na punkcie czterech dziewczyn z Tallina. W maju 2003 roku w Estonii ukazała się pierwsza płyta Vanilla Ninja i rozeszła się w 300 000 egzemplarzach. Później przyszedł kolejny sukces, gdy Vanilla Ninja związały się z niemieckim producentem Davidem Brandesem. Ich pierwszy singel Tough Enough z nowej płyty Traces of Sadness cieszył się dużą popularnością w Niemczech. Następnie wydały singel Don't Go Too Fast, a później Liar. W międzyczasie wyszła płyta Traces of Sadness. W 2004 roku z zespołu odeszła Maarja Kivi, którą z powodzeniem zastąpiła Triinu Kivilaan i szybko zyskała sympatię fanów Vanilla Ninja. Oficjalnym powodem odejścia Maarji z zespołu była ciąża. Latem 2004 roku w nowym składzie Ninjas nagrały ostatni teledysk z drugiej płyty: When The Indians Cry, w którym zaśpiewała także Triinu. Rok później przyszedł czas na nową płytę, pierwszy singel Blue Tattoo ukazał się w październiku 2004 i był kręcony na Islandii. W roku 2005 nakręciły jeszcze dwa teledyski do piosenki I Know. Wreszcie przyszedł czas na występ Vanilla Ninja w Konkursie Piosenki Eurowizji 2005 w Kijowie w barwach... Szwajcarii. Zaśpiewały tam piosenkę Cool Vibes i po wykonaniu zajęły ósme miejsce. Wkrótce wyszedł teledysk do tej piosenki. Pod koniec roku, niedługo po niezapomnianym występie w Tallinnie który odbył się 10 grudnia 2005 r. z zespołem rozstała się basistka Triinu Kivilaan. W 2006 roku Vanilla Ninja kontynuują karierę jako trio. 21 kwietnia na rynku ukazał się pierwszy singel z czwartej płyty Vanilla Ninja - Love is War (Miłość jest wojną) i nosi on tytuł Dangerzone, teledysk do niego nakręcony został w Kapsztadzie w RPA. 19 maja miała miejsce premiera Love is War. Polska premiera nastąpiła pod koniec czerwca 2006 roku. 1 września 2006 walczyły o nagrody Bursztynowego Słowika i Słowika Publiczno�ci na 42. Sopot Festiwal. Jury nie zaliczyło występu zespołu do udanych. Dziewczyny nie zdobyły żadnego ze słowików. 3 lutego 2007 roku dziewczyny biorą udział w estońskich preselekcjach do konkursu Eurowizji 2007. Jest to ich duża szansa, ponieważ mają one problemy z byłym producentem zespołu Davidem Brandesem, który posiada prawa do nazwy Vanilla Ninja oraz do wielu piosenek.