The project's name and songs were teased through a game of hangman on Bat For Lashes' social media from 15 to 22 August 2015. On the last day, Sexwitch was debuted with a surprise set at Green Man festival in Wales.
Khan and TOY had previously collaborated in 2013 to cover "The Bride", a pre-revolution Iranian song. For SEXWITCH, Khan and producer Dan Carey bought several "old weird psych records from different countries, strange folk mountain songs", and invited TOY to record cover versions of the songs. The band learned the songs and recorded them in a single take in one day. Khan asked her friends who knew Iranian, Thai, and other languages to translate the songs:
We sent out an email across friends and asked them to send back translations. Some people sent back differing translations. People’s interpretation of poetry is really interesting—sometimes you translate something really word-for-word, and other people put it into a more poetic context. I did a really quick, instinctive pulling out and underlining of things I liked, and started mixing them together to create these songs.
Khan explained why they named the project "SEXWITCH":
It came into my head because we were trying to look up beautiful Moroccan names, or names of stars or goddesses, but I thought, god, this is getting so fucking cliché, I can’t deal with this. I just thought, let’s just say what it is. When we were recording it, every time I’d do funny sex noises, me and Dan said, we’re being sexy witches. It’s a bit tongue in cheek, we’re not trying to be super cool, but I think it’s memorable. There is something very magical and dark and feminine archetypal force about it. Also, when I was singing—and this sounds ridiculous—it did feel like I was channeling some sort of ancestral feelings about witches. I kept feeling witch spirits and people that had been burned and repressed and pushed down. I just felt like I’d opened a portal—you know in Ghost, where all these dark spirits come out of the grates in the floor? I felt like something had been opened. So there is definitely a witch thing, but not because it’s now cool to be witchy and mystical, but generally about that sort of ancient feminine archetype. And also not just the feminine, not just being a woman, but there’s a quote we put in the press release because I loved it so much: about the feminine aspects in men and women, and men and women being connected to nature, power, sexuality, rebirth, regeneration. I feel like that’s in the name as well.
- "@GreenManFest we will be appearing live on the FAR OUT STAGE stage TONIGHT at 7pm." 22 August 2015. Twitter.
- Evan Minsker (10 June 2013). "Listen: Bat For Lashes' Natasha Khan and TOY: "The Bride"". Pitchfork.
- Jazz Monroe and Laura Snapes (24 August 2015). "Bat for Lashes Discusses Debut Sexwitch Album, Shares "Helelyos"". Pitchfork.
- "SEXWITCH album is out today, you can buy it on vinyl". 25 September 2015. Twitter.