ב-29 במאי באותה שנה הזמין מייק הוולט את סטינג לנגן עם להקתו, סטרונציום 90 (על שם האיזוטופ הרדיואקטיבי) בפריז, וצירף להזמנה גם הזמנה עבור קופלנד על מנת שיחליף את המתופף (כריס קאטלר) שלא היה פנוי. סטינג וקופלנד פגשו את הגיטריסט המוביל של הלהקה, אנדי סאמרס. לאחר הפגישה ביניהם רצו קופלנד וסטינג שסאמרס יצטרף לפוליס, או כפי שקופלנד אמר "מייק רצה לגנוב את הלהקה שלי, אז אני אגנוב את שלו". סאמרס עצמו רצה להצטרף אך לא רצה שאיש יפגע מהמהלך. לאחר דין ודברים הוקמה פוליס בהרכב המוכר שלה.
הקו הקשה, שנים 1977-1978.
השלישייה הופיעה לראשונה ב-18 באוגוסט 1977 בברמינגהאם ולאחר מכן עברה לסבב הופעות באירופה, שכלל את רוטרדם ופריז אך ללא הופעות של ממש, לאחר שהסתבר כי ההזמנות שדווח עליהן לא בוצעו בפועל. במהלך סיבוב ההופעות הכושל, סטינג ראה בפעם הראשונה את רובע החלונות האדומים וכתב את השיר רוקסן, שלימים הפך לאחד הלהיטים הגדולים של הלהקה.
הביקורות קטלו את הלהקה והשלישייה חזרה לבצע עבודות מזדמנות במקומות שונים. אחת מהן הוכחה כמשמעותית במיוחד, כאשר סטינג, דרך קשריה של אשתו השחקנית, השיג לשלישייה הופעה בפרסומת למסטיק, שם הם נדרשו לצבוע את שיערם לבלונד, דבר שיהפוך לסימן ההיכר של הלהקה.
השינוי הגיע כאשר קופלנד קיבל מאחיו הגדול 1500 פאונד, אשר הושקעו בלהקה. בין החודשים ינואר 1978 ויולי 1978 הקליטה הלהקה, בהפסקות רבות, את אלבומה הראשון בסטודיו הלא-מוכר אז של נייג'ל גריי. כשמיילס קופלנד הגיע לביקור באחת הפעמים הוא שמע הקלטה ראשונית של השיר רוקסן, ומיד הבין שמדובר בלהיט פוטנציאלי. הוא מכר את ההקלטה לחברת A&amp;M והחתים את הלהקה כחימום ללהקה האמריקאית ההיפית ספיריט, השונה לחלוטין בסגנונה, אך השלישייה הייתה זקוקה נואשות לחשיפה ולכסף.
רוקסן עלה לשידור באפריל 1978, אך זכה להשמעות מועטות ולא הגיע למצעדים בשל הנושא השנוי במחלוקת שבו הוא עוסק. עם זאת הוא זכה לביקורות משבחות. סטינג המשיך לעבוד על הסגנון החדש (שילוב של רוק ורגאיי), כפי שבא לידי ביטוי ברוקסן ויצר את Can't Stand Losing You, שיצא גם הוא ב- A&amp;M, ונכשל בדומה לרוקסן. לבסוף יצא אלבומם הראשון, Outlandos D'Amour (במעין שפה בינלאומית "גנבי האהבה") בנובמבר 1978, בעבור 10,000 לירות שטרלינג על חשבון זכויות עתידיות.
הלהקה יצאה לסיבוב הופעות בארצות הברית, שמטרתו הייתה ליצור כיסי אהדה בקהל של תלמידי מכללות והאזנה בתחנות הרדיו המקומיות. מיילס קופלנד הגדיר זאת במטאפורה מתחום הגרעין כיצירת מסה קריטית. ב-20 באוקטובר 1978 טסו השלושה לניו יורק. בחודש שלאחר מכן הם נסעו מאות קילומטרים ביום, ביצעו 23 הופעות ב-27 ימים, ב-200 דולר להופעה, חולקים בנהיגה עם קים טרנר, שהפך למפיק-שותף של מיילס קופלנד. מסע ההופעות לא הניב את התוצאות שלהן קיוו, אך עם זאת סייע להפוך את השלושה, שכל אחד מהם בעל אגו וכולם בעלי רקע שונה, לחבורה מלוכדת.
האלבומים הראשונים 1979-1980.
בפברואר 1979 חזרה הלהקה להקליט את אלבומה השני באולפן של נייג'ל גריי. סטינג כתב שלושה להיטים לעתיד Message in a Bottle, Walking on the Moon ו- The Bed's Too Big Without You, אבל לא היה ללהקה חומר נוסף. הם השלימו את האלבום באמצעות טיוטות של סטינג וקופלנד וקראו לאלבום "Reggatta De Blanc" (בתרגום חופשי משפה בינלאומית מומצאת - רגאיי לבן). האלבום יצא לאור באוקטובר באותה שנה והמבקרים היללו את איכות השירים של סטינג, אם כי ביקרו קשות את השירים הציניים של קופלנד. בעקבות ההשמעות ברדיו, הגיע רוקסן למקום 32 בארצות הברית, ו-A&amp;M הוציאו אותו מחדש באנגליה, שם הגיע השיר למקום 12, ואיפשר לאלבום Outlandos להגיע למקום שישי ברשימת המכירות באנגליה ו-23 בארצות הברית.
מכאן הייתה הדרך להצלחה סלולה, גם אם דרשה עבודה קשה. הלהקה יצאה למסע הופעות עולמי שנמשך שנה שלמה, עם הופעות שהחלו ב-2000 מושבים והגיעו ל-20,000 צופים בפסטיבל רדינג. בעקבות ההצלחה יצא בספטמבר Can't Stand Losing You מחדש והגיע למקום ה-2 במצעד הבריטי. Message in a Bottle, השיר הראשון מהאלבום Reggatta שיצא לאור כסינגל, הגיע בספטמבר 1979 למקום הראשון באנגליה, והאלבום עצמו היה במקום הראשון במשך ארבעה שבועות במצעד האלבומים. בדצמבר של אותה שנה Walking on the Moon הגיע למקום ראשון.
על אף ההצלחה באנגליה, הלהקה לא הצליחה לבסס את עצמה בשוק האמריקאי. מיילס קופלנד הבין שאין טעם להתעקש על השוק האמריקאי, והחליט להוציא את הלהקה למסע עולמי שאפתני: 37 ערים ב-19 מדינות. המסע החל בינואר 1980 בגרמניה, עבר לבאפלו במדינת ניו יורק בארצות הברית ומשם להונג קונג, ניו זילנד, הודו ומצרים. שתי המדינות האחרונות היו חדשות על מפת להקות הרוק, והופעות בהן היו חלוציות וזכו לתקשורת אוהדת באירופה.
סיום מסע ההופעות עבר בחזרה דרך יוון, איטליה, ספרד, גרמניה ולבסוף הופעה בעיר הולדתו של סטינג, ניוקאסל, שם 40,000 מעריצים התחרו על 4,000 מקומות באולם העירוני. לאחר מסע ההופעות היה על הלהקה לכתוב שירים חדשים כדי להקליט את האלבום הבא: Zenyatta Mondatta. סטינג פרש לביתו החדש בבוסום, הולנד והחל לכתוב שירים חדשים שלא התרכזו יותר ב"אני" אלא ב-"עולם". הוא הסביר את השינוי בכך שעד אז הוא לא ראה את העולם והמסע הוא שהרחיב את אופקיו והשפיע על שיריו.
הקלטת האלבום הייתה מלחיצה לאור הצלחת הלהקה. הם הקליטו את האלבום באולפן משוכלל בעיר הילברסום, הולנד עם נייג'ל גריי הנאמן. אבל הלחץ, המחסור בשירים, סשנים לא מוצלחים של הקלטות ועייפות של חברי הלהקה גרמו לכך שזמן ההקלטות, שנקבע לחודש ביולי 1980, לא הספיק. הלהקה סיימה את הקלטת האלבום בארבע בבוקר ביום בו הם החלו את מסע ההופעות העולמי החדש שלהם, הלכו לנוח והמשיכו מיד להופעה הראשונה שלהם בבלגיה. כל אלה, ובנוסף ריב בין גריי למיילס קופלנד על כסף, גרם לכך שגריי עזב הלהקה.
תהילה חובקת עולם 1980-1982.
עם יציאת האלבום Zenyatta Mondatta יצאה הלהקה למסע הופעות עולמי נוסף, כשהם עוצרים רק לחגוג את הצלחת האלבום באנגליה (מקום ראשון לאורך ארבעה שבועות בסתיו 1980), ובארצות הברית (מקום ב-20 העליונים במשך שישה חודשים, עם דירוג מרבי של מקום 5 ומכירות של אלבום פלטינה). גם הסינגלים הבולטים: Don't Stand So Close to Me ו- De Do Do Do, De Da Da Da זכו להצלחה ניכרת, כולל בארצות הברית, לראשונה מאז רוקסן.
מיילס קופלנד שלח אותם שוב למסע הופעות גרנדיוזי, שהחל בארגנטינה בדצמבר 1980, ולאחר מכן חזרה לאנגליה לקראת חג-המולד. בינואר 1981 הלהקה מילאה את המדיסון סקוור גארדן בניו יורק. משם הם יצאו ליפן ואוסטרליה. אבל החברים החלו להישבר, ובפברואר 1981 הם ביטלו מספר הופעות באירופה, עם שמועות על מתחים בנישואים של סטינג ושל סאמרס.
עם זאת, הלהקה החליטה להמשיך ולפעול בקצב חריג, על אף שלא הופעל עליהם לחץ מחברת ההקלטות A&amp;M. ב-15 ביוני הם החלו בהקלטת האלבום הרביעי במונטסראט שבאיים הקריביים, באולפן ההקלטות המפורסם AIR ששירת גם את הביטלס. במקום נייג'ל גריי הם מינו את יו פדהאם, מפיק צעיר אך מנוסה, שהצליח כמפיק שותף של פיל קולינס.
הפעם האלבום הוקלט בקלות יחסית, וכלל שירים רבים שסטינג כתב במהלך השנה, בשילוב של קלידים שניגנו כל חברי הלהקה בשירים שונים, וסקסופון שסטינג החל ללמוד כמה חודשים לפני כן. שם האלבום - Ghost in the Machine - הוא מושג שטבע הפילוסוף ארתור קסטלר ואשר תיאר את הפליאה וההתלהבות מכך שהטכנולוגיה באולפן מסייעת ליצור מוזיקה טובה. הצלחת האלבום והשירים הבולטים בו לא הפתיעה איש, עם Invisible Sun במקום שני באנגליה (לא יצא בארצות הברית), Ghost in the Machine במקום ראשון, Every Little thing She Does is Magic במקום ראשון באנגליה ושלישי בארצות הברית, כשהאלבום עצמו שמר על המקום השני במשך שישה שבועות. מסע ההופעות היה פחות אינטנסיבי, עם הופעות גדולות יותר ומועטות יותר ביחס לעבר, והחבורה המגובשת אפשרה לכל חבר למצוא את עצמו מחדש.
חברי הלהקה פנו כל אחד לנתיב עצמאי: סטינג פצח בקריירת משחק ככוכב הסרט Brimstone and Treacle, קופלנד כתב את המוזיקה לסרט של פרנסיס פורד קופלה Rumble Fish ולבלט "המלך ליר" שבוצע על ידי הבלט של סן פרנסיסקו, וסאמרס הקליט אלבום עם חבר נעוריו, רוברט פריפ, שהגיע למקום השישים במצעד האמריקאי.
תחילת דיבורים על גיבוש מחדש והקלטת האלבום הבא התרחשה בתקופה רעה לסטינג: הוא תבע את חברת Virgin על הפרת החוזה שלו אצלם מימיו ב-Last Exit, ובנוסף הוא נפרד מאשתו הראשונה פרנסיס, בפרידה שעירבה גם את הילדים ואת טרודי סטיילר, בת זוגו החדשה. סטינג עזב לאחוזה ששימשה את איאן פלמינג בכתיבת סדרת ספרי המתח והפעולה ג'יימס בונד בג'מייקה ושם תרגם את התקופה הרעה שעברה עליו לרצף השירים שמרכיב את האלבום החמישי - Synchronicity. הלהקה חזרה בסוף 1982 להקלטות באולפן במונטסראט ושם, לאחר ויכוחים קשים בנוגע לבחירת השירים, יצרו את האלבום שנחשב לטוב ביותר של הלהקה. הוויכוחים במהלך הקלטת האלבום זרעו את זרעי הפירוד בעתיד.
הסוף ואחריו.
האלבום החדש היה שונה מקודמיו, בין היתר בשל להקות חיקוי רבות שצצו במהלך השנים. סטינג הקליט את השיר Synchronicity כמעט לבדו, בהתבסס על מושג מהפסיכותרפיה של יונג. האלבום כלל את להיטה הגדול והמזוהה ביותר עם הלהקה: Every Breath You Take. השיר היה חלק מהתרפיה של סטינג מהשנה הקשה שעברה עליו, ומתאר את הצורך האובססיבי להמשיך לעקוב אחרי האישה שנפרדה ממנו.