Swój kolejny album artysta wydał w marcu 1996 roku i opatrzył go nazwą „Mercury Falling”. Nie osiągnął on jednak takiej popularności jak poprzedni krążek (zaledwie cztery miliony sprzedanych egzemplarzy) i został odebrany przez krytyków jako porażka artysty, który za wszelką cenę dążył do osiągnięcia komercyjnego sukcesu. Płytę promowały single takie jak „Let Your Soul Be Your Pilot” i „You Still Touch Me”. Komercyjny sukces przyszedł jednak z zupełnie innej strony. Otóż w tym samym roku jeden z bardziej znanych wykonawców czarnej muzyki – Puff Daddy, przearanżował stary przebój Stinga i The Police – „Every Breath You Take” i wydał go na swoim własnym albumie, odnosząc tym samym duży sukces. Trasa koncertowa „Mercury Falling” objęła również Polskę. 18 czerwca 1996 roku Sting wystąpił na stadionie Gwardii w Warszawie.

1997 okazał się kolejnym rokiem spod znaku filmu. „Lock, Stock and Two Smoking Barrels” w reżyserii Guya Ritchie było kinem w stylu Quentina Tarrantino jednakże w wydaniu brytyjskim. Sting, trzecioplanowy aktor, wcielił się w nim w rolę JD. W Wielkiej Brytanii film stał się jedną z najbardziej dochodowych komedii angielskich lat dziewięćdziesiątych, zaś na całym świecie zarobił około pięćdziesięciu milionów dolarów. Uznany został tym samym za najbardziej kasowy niezależny film brytyjski od czasu słynnego „Trainspotting”. Począwszy od roku 1997, aż do 2002, Sting odgrywał także epizodyczne role w bardzo popularnym, nie tylko w Stanach Zjednoczonych, ale i na całym świecie, serialu „Ally McBeal”.

27 września 1999 ukazał się kolejny, dziesiąty już solowy album Stinga „Brand New Day”. W Stanach pokrył się on trzykrotnie platyną, na świecie sprzedaż sięgnęła siedmiu milionów egzemplarzy. Krążek przyniósł artyście nagrody Grammy za Najlepszy Album Pop oraz Najlepsze Męskie Wykonanie Wokalne. Znalazło się na nim dziesięć utworów, ale dwa spośród nich wyróżniły się szczególnie. Były to: „Desert Rose” oraz tytułowy „Brand A New Day”, które stały się wielkimi przebojami na całym świecie. Obok Stinga – śpiewającego i grającego na gitarze basowej, w nagraniach uczestniczyli między innymi: Stevie Wonder na harmonijce, klarnecista Branford Marsalis, gitarzysta Dominic Miller oraz trębacz Chris Botti.

13 marca 2000 roku Sting po raz kolejny pojawił się w Polsce, promując płytę "Brand A New Day". W rok po tym koncercie, 19 czerwca 2001, ponownie zawitał do naszego kraju. W tym samym czasie artysta pojawił się również w dokumentalnym filmie Kevina Macdonalda – „Being Mick”, przedstawiającym życie codzienne jednego z największych wokalistów na świecie – Michaela Phillipa Jaggera.

11 września 2001 roku światem wstrząsnęła tragedia. Cztery tysiące osób zginęło w zamachu terrorystycznym na wieże World Trade Center w Nowym Jorku. W tym samym czasie w Toskanii Sting nagrywał swój jedenasty album. „All This Time...” był drugim oficjalnie wydanym zapisem koncertowym w karierze Stinga. Występ zorganizowany był w prywatnej posiadłości artysty i miał być transmitowany przez Internet. Wiadomość o tragedii w Nowym Jorku dotarła do Włoch wczesnym popołudniem. Dosłownie kilkanaście minut wcześniej Sting i jego żona rozmawiali telefonicznie z zaprzyjaźnionym małżeństwem, które rozpoczynało właśnie pracę w biurze Rainforest Foundation, mieszczącym się niemal na szczycie jednego z biurowców World Trade Center. Decyzja o kontynuowaniu koncertu nie była dla artysty łatwa. Sting zdecydował się jednak, że wystąpi, koncert zostanie skrócony, a transmisja internetowa ograniczy się wyłącznie do jednego utworu – „Fragile” z jakże niesamowicie w tych okolicznościach brzmiącym wersem „...nothing comes from violence and nothing ever could (nic nie bierze się z przemocy i nigdy brać nie będzie)”, będącym konstatacją naszej kruchości. „All This Time...” to koncert zupełnie inny niż wszystkie. Dowodem na to stały się później dwie statuetki Emmy.

Po 11 września Sting odszedł na jakiś czas od muzyki, przestał komponować i po raz drugi w życiu przeżywał niemoc twórczą. Musiał na nowo przemyśleć swoją pozycję autora tekstów w zupełnie innym już dla wielu świecie. Wynikiem tych rozważań stała się płyta „Sacred Love” wydana 22 września 2003 roku. Udowodniła ona po raz kolejny, iż słowa napisanych przez Stinga utworów znacznie wykraczają poza tradycyjne ramy pop–rockowej piosenki. Także muzyka: klimatyczne, spokojne i wygaszone melodie oraz smaczki pod postacią jazzowych i soulowych aranży, sprawiają, że płyta stała się w pełni dojrzałym muzycznie dziełem. Przy pracy nad krążkiem Sting ponownie połączył swe siły z Kipperem – mistrzem klawiszy i programmingu, który współprodukował również albumy „Brand New Day” czy „...All This Time”. Oprócz Kippera oraz gości takich jak: Mary J. Blige i Anoushka Shankar, na krążku zagrali również muzycy: Chris Botti (trąbka), Dominic Miller (gitary), Manu Katche (perkusja), oraz Christian McBride (kontrabas), którzy od lat są członkami jego muzycznej rodziny.

Umieszczony w Songwriters Hall Of Fame, laureat między innymi nagród takich jak: Outstandig Contribution To Music Award (przyznaną za wkład w muzykę na wyspie), nagrody imienia Ivora Novello w kategorii International Achievement (za osiągnięcia na arenie międzynarodowej), Sting tworzy już prawie 28 lat. Nie tylko na polu rocka i reggae, ale również jazzu, country, folku, elementów muzyki celtyckiej czy Środkowego Wschodu. Ma na koncie muzyczny dorobek, który podobnie jak on sam, wymyka się prostym definicjom. Niespokojny, pełen kreatywnej niecierpliwości, wciąż stawia czoła nowym oczekiwaniom. Piosenkarz i kompozytor, obywatel świata, aktywista, łowca przygód i ojciec szóstki dzieci. Sting jest żądny jutra. Każde nowe wyzwanie to rzeczywiście zupełnie nowy dzień (Brand New Day).