The writing process of The Sting has lasted over three years. Cilmi had began work on it by October 2010, mere months after the release of her second album, Ten. Teasing some information about lyrics, several ideas and feelings, she spoke on her work, saying, "It's totally exciting because I am spending a bit more time with this record. I want to see what works. I really love Dolly Parton, roots music, Tricky and Enya, so anything could happen."
On 18 January 2012, Cilmi debuted a Sam Wrench-directed video for an "acoustic-ish" version of "Vicious Love", the first song she wrote for the album. Cilmi explained, "If you've ever experienced any type of 'Vicious Love' you will know that sometimes despite all the arrows pointing to a dead end there is just no way out, there is no way back. But then again don't all roads lead to dead ends? [...] Guess we should just enjoy the ride..."
Gabriella began writing and recording with members of her live band. "I was searching for a sound that reflected the way I felt inside, which was quite vulnerable, and traumatised. I wanted it to sound the way Italian neo-realist photographs look, that post-war, ruined glamour which is really gritty and heart-breaking. I was listening to a lot of Trip Hop, that 90s Bristol sound, Portishead and Tricky. But also singer-songwriters I had always loved, Neil Young, John Martyn. And old soul records, Bessie Smith, Otis Redding. It all went in there." In an interview with Billboard about the process of making 'The Sting', Gabriella stated, "The whole idea of 'The Sting' came as an aftermath to breaking-up with my label, and management and boyfriend at the time. The lyrics side of things were influenced by what I was going through. It was all a bit of a sting. But nothing killed me." 
A black-and-white music video for "Sweeter in History", filmed in the Italian towns of Valvori and Cassino, was released on 14 March 2013. On 26 March, the track was offered as a free download for a limited time.
"The Sting" was released on 1 September 2013 as the album's official lead single, for which a music video was also directed by Wrench.
The second single, "Symmetry", was released on 11 November 2013. The accompanying music video premiered on 17 September.