W latach 1969-1971 klub występował pod nazwą ŻSK-Sławia, po połączeniu z DFS "Łokomotiw" (założonym w 1929 roku).
Drużyna największe sukcesy odnosiła przed II wojną światową oraz w latach 50. i 60. XX w., kiedy to czterokrotnie zdobyła Puchar Armii Radzieckiej i – w sezonie 1966–1967 – dotarła do półfinału Pucharu Zdobywców Pucharów, w którym uległa Rangers. Ostatni tytuł mistrza kraju wywalczyła, po ponad pięćdziesięcioletniej przerwie, w 1996 roku.
Od grudnia 2006 do lipca 2007 roku szkoleniowcem Sławii po raz drugi był Aljosza Andonow, który zastąpił Serba Ratko Dostanicia. Przed rozpoczęciem sezonu 2007-2008 jego miejsce zajął były piłkarz Partizana Belgrad, Macedończyk Stevica Kuzmanovski, poprzednio pracujący w OFK Beograd i Belasicy Petricz.
Sukcesy Mistrzostwo Bułgarii: 7 1928, 1930, 1936, 1939, 1941, 1943, 1996 Wicemistrzostwo Bułgarii: 10 1926, 1932, 1934, 1950, 1954, 1955, 1959, 1967, 1980, 1990 Puchar Bułgarii: 2 1996, 2018 Puchar Armii Sowieckiej: 6 1952, 1963, 1964, 1966, 1975, 1980 Puchar Bałkanów: 2 1986, 1988 Występy międzynarodowe: półfinał Pucharu Zdobywców Pucharów 1966-67, ćwierćfinał Pucharu Zdobywców Pucharów 1980-81
Europejskie puchary