Майлз Копленд, хотя официально и не был менеджером, завершил все переговоры со студией от имени группы. Сначала он предложил Найджелу Грею две тысячи фунтов по завершении записи или процент от продаж альбома, если тот готов ждать. Грей остановился на двух тысячах фунтов, но затем потратил много месяцев, пытаясь выжать эти деньги из Майлза.
Группа решила, что альбом должен называться «Outlandos D'Amour» («Заморская любовь»). Иногда Майлз забегал в студию посмотреть на предмет своих инвестиций. В первый раз, когда он приехал в Лезерхед, группа только что завершила композицию «Будь моей девушкой». Майлз ненавидел ее и возмущённо заявил, что это звучит как «Curved Air» пятилетней давности.
Однако в следующий раз Майлза встречали звуками «Роксаны». Он был, можно сказать, потрясен песней, схватил копию записи, обещая использовать ее для того, чтобы обеспечить группе хорошую сделку.
Майлз принес пленку в «А&М Records», где одна из его других групп, «Squeese», уже получила хороший контракт. Копленд убедил их выпустить «Роксану» синглом. У группы поднялось настроение, когда они услышали хорошую новость. Их неприязненное отношение к Майлзу сразу же улетучилось. Даже Стинг признает: «Под руководством Майлза мы совершили нашу первую сделку с записывающей компанией, которая принесла нам материальную свободу. Уж если мы двинулись вперед, нас уже было не остановить».
Сделка, проведенная Майлзом Коплендом, оказалась удачной. Он фактически отдал «А&М Records» этот сингл, не требуя никакого аванса на том основании, что он верит, что продажи будут столь высокими и группа заработает гораздо больше на гонораре. Они в конце концов сделали миллионы только лишь с этой записи! Майлз Копленд предпринял чрезвычайно рискованное дело и доказал, что он великолепный менеджер и умеет прекрасно вести переговоры.
Этот всплеск энтузиазма Майлза вскоре принес им тьму «живых» выступлений. Они поддерживали американскую группу «Spirit» на трех знаменательных для Британии датах в марте того года. Однако Майлз все еще не был официальным продюсером «Полиции». Это был постепенный процесс, и он брал на себя все больше и больше руководящих функций в группе.
Майлз уже создал впечатляющую плеяду успешно выступающих групп, включая «Vishbone Ash», «Renaissance», «The Climax Blues Band» и «А1 Stewart». Однако как раз тремя годами ранее, в 1975 году, возникло неустойчивое положение, и ему пришлось ликвидировать дело. «Тогда я узнал, что достичь вершины не так трудно, как остаться там», — объяснял он позже. «Самой большой западней является то, что у вас есть несколько хитов, и вы думаете, что это навсегда, и позволяете себе расслабиться».
Майлз всегда очень скромничал по поводу того, какую он сыграл роль в старте «Полиции». «Просто случилось так, что я дал им старт. Если бы меня не было там, они все равно бы это сделали».
Наконец-то «Полиция» приобрела лицо и форму. Запись «Outlendos» продолжалась двухдневными рывками на протяжении первой половины 1978 года. Когда люди впервые услышали музыку из альбома, они не сразу восприняли так называемый «белый» регги, который вызвал критику представителей разных кругов музыкальной индустрии. Однако Стинг считал, что ничего такого не сделал, а просто приспособил регги к своим собственным находкам. «В моей голове две формы могли существовать параллельно, и звучало это хорошо. Темп мог внезапно поменяться. Затем, когда мы начали прогрессировать, эти два стиля слились», — пояснял Стинг.
«Роксана» вышла 7 апреля 1978 года и получила благоприятные отзывы. Но ее мало передавали по радио, потому что составители программ неохотно использовали песню о любви к проститутке.
Мнение Стинга о своем шедевре интересно. «Я ощущал сильные чувства к песне «Роксана», потому что это была серьезная песня о реальных отношениях. В этой песне не говорилось о грубом сексе. Это не была «грязная песня» ни в каком значении этого слова. Это была настоящая песня, с настоящей лирикой, а они не проигрывали эту песню на том основании, что она была о проститутке. Но напишите глупую песню о сексе, в которой самого этого слова нет, и вы получите хит. Как это раздражает».
Стинг был настолько приведен в восторг записью «Роксаны», что почувствовал вдохновение для написания «Я не могу потерять тебя». «А&М Records» были все еще настолько не уверены в этой группе в целом, что они попытались подправить дорожку записи до ее выхода, и только позже поняли, что ошиблись, и выпустили оригинальную версию.
Последовал еще один визит в Мюнхен к Эберхарду Шунеру, но на этот раз вокальные номера Стинга стали доминировать в немецком проекте. Шунер позже утверждал даже, что он учил Стинга, как петь, но нет сомнения, что Стинг знал, что он делает, задолго до этого.