Стилян Петров начал свою карьеру в ФК Монтана. Через год после своего профессионального дебюта он перешел в ЦСКА и вскоре ворвался в первую команду.
Он быстро стал одной из ярких молодых болгарских звезд, в 1999 году дебютировал за сборную своей страны.
Его выступления быстро привлекли внимание ведущих клубов Европы, спустя некоторое время он перешел в шотландский Селтик.
Стилян очень быстро сумел доказать свой класс и был признан лучшим молодым игроком шотландской шотландской лиги в 2001 году.
Петров был капитаном болгарской национальной команды и выступал за сборную на Евро 2004.
Когда бывший главный тренер Селтика Мартин О'Нил был назначен коучем Астон Виллы, Петров без колебаний принял предлодение перейти на Вилла Парк незадолго до закрытия трансферного окна за 6,6 млн. фунтов стерлингов.
Дебютировав в игре против "Вест Хэма" в сентябре, болгарин выступал очень неплохо в начале сезона 06/07.
Несмотря на то что он сыграл 60 матчей за сборную своей страны, в октябре 2006 года Петров шокировал болгарских болельщиков футбола, приняв решение уйти из национальной сборной в возрасте 27 лет из-за конфликта с гланым тренером сборной Болгарии Христо Стоичковым.
Однако, всего лишь несколько месяцев спустя Стилян Петров уладил свои разногласия с тренером и вновь вернулся в сборную.