Na kolejny wielki sukces nie trzeba było długo czekać. W 1993 roku Sting i Michael Kamnen ponownie połączyli swe siły i wraz z Bryanem Adamsem i Rodem Stewartem napisali piosenkę „All For Love”, promującą disneyowską tym razem wersję „The Three Musketeers”. Z założenia „skazany” na łatwy sukces kasowy, przebojowy utwór gwiazd rocka, szybko odniósł dużą popularność. Krytycy natomiast podzielili się w swych opiniach na dwa skrajne obozy. Jedni nazwali go: niezbyt udanym artystycznie, inni natomiast szybko przypisali mu określenie: pięknej piosenki, która stała się symbolem nowego kierunku w twórczości Stinga. Bez względu jednak na wszelkie opinie, utwór podbił serca milionowej publiczności na całym świecie i podobnie jak „It's Probably Me” stał się komercyjnym strzałem w dziesiątkę.

Dzięki tym sukcesom rok 1993 dla muzyki filmowej okazał się rokiem Stinga. Coraz więcej reżyserów chciało mieć piosenkę promującą film napisaną właśnie przez niego. Do tej grupy zaliczał się między innymi Luc Besson, który za zgodą autora w tym samym roku umieścił jedną z jego kompozycji w filmie „Leon Zawodowiec”. Poszerzona o gitarowe intro w wykonaniu znakomitego gitarzysty Dominica Millera piosenka „Shape Of My Heart” okazała się genialnym podsumowaniem wzruszającej historii przyjaźni płatnego zabójcy, którego zagrał Jean Reno i osieroconej tragicznie dziewczynki (Natalie Portman). Dziwi więc niezmiernie fakt, że pomimo, iż utwór stał się wręcz nierozerwalną częścią filmu, bez której on sam wiele traci, z niewiadomych powodów nie znalazł się on na wydanej do niego ścieżce dźwiękowej. A jednak zdecydowana większość muzycznych odbiorców, jak i miłośników muzyki kina, kojarzy piosenkę właśnie z tym filmem, choć tak naprawdę pochodzi ona z wydanej niewiele wcześniej solowej płyty Stinga – "Ten Summoner's Tales" z 1993 roku.

W tym samym roku powstał jednak inny znakomity soundtrack Stinga do filmu „Demolition Man”. Piosenkę o tym samym tytule w 1981 roku nagrała grupa The Police. Dwanaście lat później ten stary przebój okazał się wręcz idealny do filmu o Człowieku Demolce z Sandrą Bullock, Wesley Snipesem i Sylvestrem Stallone w rolach głównych. Opowiadał on bowiem o bestii tkwiącej wewnątrz każdego z nas i o naszej destruktywnej naturze(3). Aby jednak mógł się on stać piosenką promującą film, Sting podjął się zadania kompletnego przearanżowania i unowocześnienia utworu. Stąd więc jej nowy charakter i nowoczesne brzmienie zupełnie nie przypominające tego z czasów The Police. W Polsce film z utworem Stinga obejrzeć mogliśmy już na początku 1994 roku.