With the days of punk fast approaching, Stewart decided to form a new band fashioned on the vibe and energy of punk music. He wanted to create a trio based on drums, guitar, and bass and already had a guitar player lined up, a Corsican named Henry Padovani. Stewart called his new project The Police, a provocative name in its time that capitalized on the everyday brawls that broke out between punks and law enforcement: a regular police presence in the streets of London meant free marketing for his band.

A Curved Air performance in Newcastle gave Stewart the chance to catch the set of a local band called Last Exit, a popular jazz fusion band that journalist Phil Sutcliffe had wanted him to see play. Only one thing caught Stewart's attention at the concert that night: the stage presence of the band's charismatic bass player, a musician called Sting. This was the third piece that Stewart needed to complete his Police project.

Phil introduced the two musicians after the show, and Stewart gave Sting his phone number, instructing him to give him a call if he were ever in London in search of a place to stay and a band to join. When Sting finally decided to leave Newcastle to try and make it as a musician, he had no plan and no idea what might happen: he went to London with only Stewart's phone number in his pocket and his wife, actress Frances Tomelty, and their young child in tow.

Stewart was happy to receive Sting's call and invite him into the band but was concerned how Sting and Henry—with their different approaches to music and their instruments-would get along: Sting was a sophisticated musician with a jazz background, while Henry was a classic punk guitarist with lots of energy but little else. Punk had become the mainstream of the day and demanded Henry's vibe and spirit, but Stewart soon realized that this wasn't the situation that Sting was looking for.

In those early days, songs for the Police were written primarily by Stewart with a little help from his brother Ian. "Fall Out" and "Nothing Achieving," the band's first single and B-side, were written by both.