Przez cały ten okres pracy i nauki Gordon odwiedzał wieczorami kluby muzyczne, szczególnie The Wheatsheaf, w którym czasem zastępował basistę lokalnego zespołu The Phoenix Jazzman. Ernie miał taki wielki kontrabas. Grałem czasem dwa kawałki, a odciski nie schodziły mi z palców tygodniami(7). Wcześniej podjął dwie nieudane próby założenia swoich własnych zespołów. Pierwszy z nich powstał w 1969 roku, a ponieważ liczył zaledwie dwie osoby (włącznie z Gordonem) i grał coś w rodzaju wysublimowanego jazzu, szybko więc zakończył swoją karierę na kilku uroczystościach urodzinowych i potańcówkach. Kolejny zespół nosił nazwę Earthrise, ale i ta grupa nie odniosła nawet śladowego lokalnego sukcesu, choć była o tyle ważna, że dzięki niej młody basista nawiązał kontakt z wcześniej wspomnianym sekstetem The Phoenix Jazzman. Któregoś wieczoru basista Ernie w ogóle się nie pojawił i Sting zagrał cały koncert na swoim elektrycznym basie.

W tym okresie właśnie, puzonista zespołu, nazwał Gordona - Stingiem(8). Wzięło się to od czarno-żółtego swetra w pasy, który wówczas nosił. Sting szybko zyskał uznanie bractwa jazzmanów z Newcastle, co potwierdziło zaproszenie do współpracy z The Riverside Men, a następnie Newcastle Big Band. Z tym też zespołem po raz pierwszy w życiu nagrał niskonakładowy album oraz pozyskał swój pierwszy angaż zagraniczny. Zdawałem sobie sprawę, że odbywam coś w rodzaju stażu czeladniczego. Nauczyłem się czytać nuty i dużo codziennie ćwiczyłem W dalszym ciągu studiowałem i jednocześnie co noc zarabiałem fortunę. Miałem nowy samochód i byłem naprawdę kimś w College’u(9).

W 1972 roku Sting założył swoją własną grupę – Last Exit, w skład której weszli członkowie The Newcastle Big Band: Jerry Richardson, John Hendley i Ronnie Pierson. Wtedy właśnie po raz pierwszy w życiu zaczął komponować i śpiewać. Robił to z wielką chęcią, szczególnie dla irlandzkiej aktorki Frances Tomelty. Poznał ją podczas kontraktu grupy Last Exit, grającej w rockowych przedstawieniach bożonarodzeniowych w grudniu 1974 roku. Dwa lata później 1 maja 1976 Sting i Frances wzięli ślub. W tym samym czasie porzucił pracę w szkole, w której pracował przez dwa lata i przeszedł na zasiłek. 23 listopada urodził im się syn, którego nazwali Joseph na cześć ojca Frances. Ich córka przyszła na świat sześć lat później, 17 kwietnia. Last Exit zapewnił sobie lokalny sukces, a Sting podpisał pierwszy w życiu kontrakt z Londyńską wytwórnią Virgin Music. To nie był dobry kontrakt, byłem jednak tak podniecony, że zdecydowałem się na podpisanie umowy. Myślałem: teraz jestem prawdziwym autorem piosenek, mogę rozmawiać z ludźmi o moich wydawcach – to było niezwykłe(10). Późniejsze reperkusje owego kontraktu miały doprowadzić Stinga i szefa Virgin - Richarda Bransona do rozprawy sądowej. Na jednym z koncertów Last Exit pojawił się Steward Copeland grający w okolicy ze swoim własnym zespołem – Curved Air. Grupa nie zrobiła na nim większego wrażenia, zauważył natomiast fantastyczną osobowość sceniczną wokalisty. Sting nie potrzebował zbyt wiele namysłu, aby przystać na zaproszenie Copelanda i przenieść się wraz z rodziną do jego domu w Londynie. Ten natomiast miał wobec niego znacznie większe plany. Wszyscy mówili, że zwariowałem. Moi rodzice, dyrektor szkoły i ludzie, z którymi pracowałem. Wszyscy powtarzali że oszalałem, ponieważ mając żonę i dziecko na utrzymaniu rzuciłem płatną pracę, ewentualną emeryturę i bezpieczną niszę życiową. Ja wiedziałem jednak ze muszę zdecydować się na ten przełom(11). A takim stać się miała grupa The Police założona przez Copelanda wkrótce po przybyciu Stinga do Londynu. Jej pierwszy koncert odbył się w londyńskim Music Machine 25 czerwca 1977 roku. Henriego Padowaniego, pierwszego gitarzystę zespołu już w sierpniu zastąpił znacznie lepszy Andy Summers. Z pieniędzy uzbieranych dzięki sprzedaży nagranego cztery miesiące wcześniej singla zatytułowanego „Fall Out” oraz dzięki finansowemu wsparciu pierwszego managera zespołu – Milesa Copelanda, The Police wynajęło studio i 13 stycznia 1978 roku rozpoczęły się nagrania. 31 grudnia 1977 roku Sting zorganizował przyjęcie sylwestrowe. Dobiegał końca ostatni rok, w którym twarz Gordona należała wyłącznie do niego(12).