Благодаря Филиппу Киркорову мир узнал Анастасию Стоцкую, как талантливую певицу. Хотя в этом основная заслуга принадлежит самой певице, ведь, как известно, талантливый человек бывает  талантлив во всём. Не имея большого вокального опыта, тем не менее, в 2003 году Анастасия становится победительницей конкурса «Новая волна» в Юрмале.

Как считает сама певица, она победила больше не за счёт вокальных данных, а благодаря своему актерскому мастерству, ведь у неё уже был богатый сценический опыт. Там, на сцене, Анастасия исполнила песню «Вены-реки», которая произвела среди зрителей настоящий фурор! Публика несколько минут не давала певице уйти со сцены, такие овации вызвало её выступление.

Но эту победу нельзя назвать лёгкой. Анастасия усиленно занималась вокалом с Машей Кац и Филиппом. Они всегда помогали начинающей певице, подсказывали, направляли в нужное русло.

Позднее на песню «Вены-реки» был снят видеоклип. Конечно, его популярность не стала неожиданностью: он долгое время занимал первые места на различных музыкальных телеканалах.

В течение всего года, после своей триумфальной победы в Юрмале, Анастасия Стоцкая объездила практически всю Россию, а так же ближнее и дальнее зарубежье. В общей сложности Стоцкая дала около трёхсот концертов.

В 2005 году одним из модных греческих композиторов Димитрисом Контопулосом и поэтом Димитрисом С. для Анастасии Стоцкой была написана песня «Shadows Dance All Around Me», с  которой она участвовала в «Евровидении-2005».

Её подготовку возглавил известный как в самой Греции, так и за её пределами продюсер Элиас Псинакис. Как раз таки под его чутким руководством в финале конкурса Анастасия заняла третье место.