W 1994 został wybrany do Zgromadzenia Narodowego 37. kadencji, mandat poselski złożył jednak rok później w związku z objęciem stanowiska burmsitrz Sofii. W lutym 1997 po dymisji rządu Żana Widenowa prezydent Petyr Stojanow powierzył Stefanowi Sofijanskiemu misję utworzenia nowego, tymczasowego gabinetu, który kierowałby administracją państwową do czasu majowych wyborów.
Stefan Sofijanski pozostał burmistrzem Sofii. W 2001 wystąpił ze Związku Sił Demokratycznych, powołując własną partię – Związek Wolnych Demokratów. Ugrupowanie to pozostało w Zjednoczonych Siłach Demokratycznych, a w 2005 współtworzyło blok wyborczy pod nazwą Bułgarski Związek Ludowy. W wyborach w tym samym roku jego lider został wybrany do Zgromadzenia Narodowego 40. kadencji, odchodząc z urzędu burmistrza. W tym czasie pojawiły się oskarżenia o korupcję i przestępstwa urzędnicze z okresu zarządzania miastem, w każdym z trzech procesów karnych zostawał uniewinniony od popełnienia zarzucanych mu czynów.