Первой «взрослой» победой Подольской стал Гран-При на конкурсе-фестивале «Золотой Шлягер – Могилев`99». В том же году Наташа поступила на юридический факультет Белорусского Института Правоведения, который закончила с красным дипломом.

Позже Наташа стала финалисткой Национального телевизионного фестиваля песни «На перекрестках Европы». Но по-настоящему широкая известность пришла к Подольской в 2002 году, после участия в конкурсе «Славянский Базар» в Витебске, на котором она завоевала 3-ю премию. Осенью того же года Наташа стала участницей ежегодного международного фестиваля в Праге. Это проводится среди лауреатов национальных конкурсов FIDOF (международного сообщества организаторов музыкальных фестивалей), и называется «UNIVERSETALENT». Достаточно сказать, что Америку в нём представлял Майкл Джей – продюсер, композитор, обладатель «Grammy», автор многих песен, исполняемых Kylie Minogue и Celine Dion. Итогом Наташиного выступления стали две премии в номинациях: «Лучшая песня» и «Лучший исполнитель». На этом конкурсе произошло знакомство Натальи Подольской и Майкла Джея, впоследствии получившее творческое продолжение.

В 2002 году Наташа переехала в Россию и продолжила музыкальное образование, поступив на вокальное отделение Московского Института Современного Искусства, где уроки певческого мастерства ей преподавала Тамара Миансарова. Параллельно с певческой практикой Подольская занималась в танцевальной школе «Стрит-джаз» под руководством Сергея Мандрика. В Москве Наташа начала работу над записью сольного репертуара. Вскоре после того, как в студии ГЦКЗ «Россия» были записаны её первые песни, на CD «Выпускник 2002», среди таких имен как Лариса Долина, Филипп Киркоров и Олег Газманов, впервые появилось имя Натальи Подольской (песня «Ночь и день»).

В начале 2003 года Райан Лобшер и Майкл Джей специально для Наташи написали песню «Unstoppable», с которой она участвовала в отборочном конкурсе «Евровидение-2004» в Белоруссии. К сожалению, финал этой истории не был удачен. После голосования телезрителей в отборочном туре Наталья значительно опережала остальных претендентов, но в результате фальсификации итогов (которая впоследствии была юридически доказана), на конкурс были отправлены другие исполнители.

В 2005 году впервые в России отборочный тур международного музыкального конкурса «Евровидение» прошел путем интерактивного голосования. На финишной прямой серьёзная борьба за лидерство шла между Анастасией Стоцкой, Димой Биланом и Натальей Подольской. В решающий момент Наташин рейтинг оказался выше и, в результате, 21 мая 2005 года на международном музыкальном конкурсе «Евровидение-2005» в Киеве Россию представляла Наталья Подольская с песней «NOBODY HURT NO ONE» («Не причиняйте друг другу боль»). Музыку песни написал композитор Виктор Дробыш, текст - американка M.S. Applegate и финн J.P. Chase.

В мае в рамках подготовки к участию в конкурсе «Евровидение» Наталья Подольская участвовала в промо-туре по зарубежным странам: Греция, Бельгия, Хорватия, Болгария, Молдова, Украина, Белоруссия. В промо-туре Наташа принимала участие во всевозможных пресс-конференциях, концертах, телешоу и интервью на радиостанциях и телевидении.

Съемки клипа на песню «NOBODY HURT NO ONE» проходили в известном финском рок-клубе «Tavastia». Режиссером клипа стал Игорь Бурлофф, художником-постановщиком – Жора Ничри.

В видеоклипе Наталья предстала в новом образе, серьезном и смелом. Сценический имидж певицы тщательно разрабатывался известным стилистом Натальей Пилат. В результате, черный топ с открытой спиной, короткие джинсовые шорты и черные сапоги на шпильке со шнуровкой прекрасно подошли к ее огненно-рыжим волосам и прямой челке.

Продюсер и композитор Натальи Виктор Дробыш принял непосредственное участие в подготовке к съёмкам клипа. Он собрал состав музыкантов - барабанщика и гитариста известной финской группы Killer и своего сына, гитариста Валерия Дробыша. В таком же составе «группа поддержки» выступила на финальном концерте «Евровидения-2005».

Итак, 21 мая в Киеве прошёл финал конкурса «Евровидение -2005». Наталья Подольская выступила под номером 20. Наши соотечественники, которые смотрели трансляцию «Евровидения» по Первому каналу, не смогли голосовать за нашего исполнителя – таковы правила – но ничто не помешало им болеть за Наташу!

Выступление Наташи Подольской было встречено на ура российскими продюсерами и музыкальными критиками, их отклики говорили о том, что номер Наташи выше всяких похвал. Однако, к огромному сожалению, политика оказалась сильнее и в результате конкурса «Евровидение» Подольская оказалась лишь на 15 месте.

Международный музыкальный конкурс «Евровидение» закончился не так удачно, как нам того хотелось, однако конкурс внёс свой вклад в творческое развитие восходящей звезды. У Натальи Подольской появилось огромное множество друзей из других стран. Уже этой осенью Наташа будет принимать участие в различных музыкальных фестивалях по всей Европе. Также Подольской поступило не мало предложений от зарубежных авторов, которые предложили ей исполнить свои песни.

В данный момент активно кипит работа над новым, уже вторым альбомом Натальи Подольской. Уже готовы и записаны 6 песен, среди которых «Одна» и «Выключи свет». Снят клип на песню «Одна». В июне 2006 года Наталья Подольская и Владимир Пресняков записывают дуэтную песню "Стена" (В.Пресняков-мл. / И.Резник).