A dal teljesen a kettes szám „bűvkörében” mozgott, hiszen a zenekar második, „Reggatta De Blanc“ című stúdióalbumán kapott helyet, amelyről a második kislemezként jelent meg, hogy másodszorra is a slágerlista élére repítse Stingéket.  A „Walking on the Moon“ –hoz készült klipet a The Police stílusosan nem máshol, mint a Kennydy Űrközpontban forgatta.

A „Walking On The Moon” születéséről Sting két eltérő történettel is szolgált az évek során. Nem sokkal a dal megjelenését követően, 1981-ben egy interjúban arról beszélt, hogy egy müncheni koncert után, részegen pattant ki a fejéből a dal ötlete, amire még másnap(osan) is emlékezett, és meg is írta. 2003-ban megjelent életrajzában pedig azt írj, hogy a „Walking On The Moon”-t az első barátnője, Deborah ihlette, az érzés, amikor az ember felhőtlenül szerelmes és a fellegekben jár.

Fotó: John Rodgers/Redferns/Getty Images