Służba thumb|Krążownik „Sława” na Morzu Śródziemnym, 1986 rok thumb|„Moskwa” w 2009 Po wejściu do służby 7 lutego 1983 roku okręt przydzielono do Floty Czarnomorskiej, z bazą w Sewastopolu. Kilkakrotnie pływał po Morzu Śródziemnym na tzw. służbie bojowej, śledząc okręty państw NATO. W kwietniu 1985 roku, gdy pełnił służbę na Morzu Śródziemnym u wybrzeży Libii, doszło do pożaru na pokładzie. Między 27 maja 1986 a 20 lutego 1987 roku krążownik operował na Morzu Śródziemnym i północnym Atlantyku; w tym czasie w listopadzie 1986 roku odbył wizytę w Pireusie. Nosił zmienne numery burtowe: 126 (1983), 108 (1984), 106 (1987), 121 (1990).
W dniach 2–3 grudnia 1989 roku „Sława” uczestniczyła w szczycie na Malcie, będącym pierwszym spotkaniem radzieckiego przywódcy Michaiła Gorbaczowa i prezydenta USA George′a Busha, który przybył na krążowniku USS „Belknap”. Część spotkań miała odbyć się na pokładzie „Sławy”, lecz zostało to uniemożliwione przez złą pogodę.