Invisible Empire/Crescent Moon was produced by Tunstall with the American singer-songwriter, musician and record producer Howe Gelb. The pair first met after they were both invited by Robyn Hitchcock to join a touring show called The Floating Palace. She and Gelb hit it off, "He's just such good fun," said Tunstall. "He's mischievous and he's a maverick and he's got a great bad attitude towards convention and is musically very exciting."
Gelb invited Tunstall to record in his studio in Tucson, Arizona. She recorded Invisible Empire/Crescent Moon there during two separate sessions in April and November 2012. This woozy, hypnotic blues tune emerged during their first period. "It's about basically knowing your potential," explained Tunstall, "knowing you're great, but not being able to see it through because of your own insecurities and not feeling a support system around you."