The song's lyrics were inspired by the addiction and recovery of one of Carlile's friends while the style was influenced by Elton John, The Beatles and Sheryl Crow. The song is written from the viewpoint of the addict, and addresses the healing process and reconciliation that comes with overcoming addiction.
On March 19, 2012, "That Wasn't Me" was announced along with Carlile's fourth studio album via her official website. The announcement stated that the single would be sent to radios soon. On March 26, via social networking site Twitter, Carlile "tweeted" the single cover and announced that the single would be released online on April 3.