kroz rad sa legendarnim makedonskim bendom Leb i sol, koji je čitave dve decenije pre etno-world buma u svetu kombinovao lokalne folklorne kolorite i izlomljene južnjačke ritmove sa rok, pop i džez elementima. Originalnost i kvalitet benda i danas se mogu proveriti preslušavanjem bilo kog od ukupno14 snimljenih albuma, uključujući i dva live, kao i dupli "Antology", kojim je Leb i sol 1996. i zvanično prestao da postoji. U solo vodama Vlatko se snašao jednako dobro, pa je još i pre razlaza benda objavio samostalni album "Cowboys and Indians". Česti izleti u svet filma i pozorišta rezultovali su albumima "Sarajevo" sa muzikom za istoimenu predstavu koju je napisao njegov rođeni brat Goran, a režirao Slobodan Unkovski, kao i soundrackom za film "Gypsy Magic" Stoleta Popova, odakle je skinut i do sada najuspešniji singl ovog muzičara - "Giypsy Song". Najviše pažnje ipak je posvetio svom novoformiranom bendu, sa kojim je 1998. objavio i album pod jednostavnim nazivom "Vlatko Stefanovski trio". U međuvremenu, pojavio se i na albumu splitskog kantautora Džibonija, u probranom društvu najkvalitetnijih svetskih sešn-muzičra kao što su Manu Katche, Pino Paladino, Tony Levin i Geffrey Oriema, sa kojima je i kasnije uspešno sarađivao na svom narednom solo-albumu "Kula od karti". Najveće umetničke domete Vlatko je ostvario kroz saradnju sa Miroslavom Tadićem, "bratom blizancem" iz zemlje gitara - Kalifornije. Album "Krushevo" je u idealnoj srazmeri pomirio uticaje balkanske muzike sa nasleđem najslavnijih svetskih gitarskih virtuoza poput Paca DeLucie, Alla DiMeole ili Allana Holdswortha. Kao proizvod saradnje ova dva vrsna muzičara, 2004. se pojavio i za sada poslednji Vlatkov objavljeni studijski rad, album "Treta majka". U poslednje vreme šuškalo se o ponovnom okupljanju grupe Leb i sol, što se konačno i ostvarilo, ali su Bodan Arsovski, Garabet Tavitijan, Koki Dumiševski i Vlatko Stefanovski to učinili samo privremeno i namenski, kako bi kroz nekoliko nastupa sakupili dovoljno materijala za koncertni DVD. Na festivalu Exit 06 ponovo će nastupiti Vlatko Stefanovski trio.