Il batterista Robby Staebler si trovò costretto a vivere in auto e a vendere tutti i suoi averi per potersi trasferire da Portland a Nashville per suonare nella band di un suo conoscente. Tuttavia, egli si risolse poi ad abbandonare il progetto a causa di problemi personali coi rimanenti membri del gruppo. Frattanto, Staebler aveva avuto modo di comporre una piccola raccolta di otto brani musicali e si era quindi messo alla ricerca di musicisti che potessero permettergli di dare forma a una sua idea di un nuovo gruppo musicale.
Staebler reclutò a tal fine il chitarrista Ben McLeod, convinto delle sue abilità dopo aver assistito a un'esibizione in un bar dove suonava una chitarra con lo slide. Il duo appena costituito si cimentò nella composizione di musica jazz. Staebler si ritrovò poi a lavorare in un negozio hippy insieme a quello che sarebbe presto divenuto il bassista del gruppo: Charles Michael Parks Jr. Questi, dopo aver ascoltato i brani composti dal duo, si convinse a sua volta delle abilità di Staebler e McLeod e decise di unirsi alla band. Il gruppo, ormai diventato un trio, abbandonò il proprio genere iniziale per occuparsi di musica più marcatamente heavy.
Il loro primo omonimo EP, contenente quattro brani, fu autoprodotto e immesso in circolazione nel 2012. Gli All Them Witches furono anche il primo gruppo statunitense a siglare un contratto con la casa discografica tedesca Elektrohasch Schallplatten. Nel febbraio del 2013 uscì presso questa etichetta il loro album di debutto, intitolato Our Mother Electricity (lett. "La nostra madre elettricità"), contenente nuove versioni di alcuni pezzi apparsi sul primo EP e la copertina realizzata da Mat Bethancourt.
Nel corso del 2013, il gruppo pubblicò sulla propria pagina Bandcamp sia un EP autoprodotto – Extra Pleasant, lett. "Stra-piacevole" – sia il proprio secondo album, sempre autoprodotto: Lightning at the Door (lett. "Illuminazione alla porta"), che più tardi fu preso in distribuzione dalla Tone Tree Music. È del febbraio del 2015 un album autoprodotto con una raccolta ufficiale dei loro concerti dal vivo: At the Garage (lett. "Al garage").
Dal 2015
Nell'estate del 2015, il gruppo siglò un contratto con la New West Records. Lo stesso anno, venne anche pubblicato il primo album con la casa discografica, nonché terzo album in studio, Dying Surfer Meets His Maker (lett. "Un surfer moribondo va incontro al suo creatore"); l'album fu registrato in una baita tra le montagne del Tennessee, dove i membri si isolarono appositamente per sei giorni. Il titolo dell'album richiamava quello di una canzone che doveva far parte di un progetto solista di McLeod, Woodspitter (lett. "Sputalegna"), ispirato a un incidente reale in cui il chitarrista aveva messo a repentaglio la propria vita mentre surfava.
Nell’arco del 2016, l’album Lightning at the Door, precedentemente autoprodotto, fu ripubblicato dalla New West, seguito a settembre dall’album Live in Brussels che conteneva la registrazione del concerto tenuto dal gruppo a Bruxelles nel marzo 2016. A meno di sei mesi di distanza, nel febbraio 2017, Dave Cobb, che in precedenza aveva lavorato con artisti del calibro di Sturgill Simpson e Chris Stapleton, produsse il loro quarto album in studio, Sleeping Through the War (lett. "Dormendo nel corso di una guerra"). Per la realizzazione dell'album prestarono le loro voci tre cantanti di Nashville: Caitlin Rose, Erin Rae e Tristen.
A metà del 2018, il gruppo annunciò che Jonathan Draper avrebbe sostituito Allan Van Cleave alla tastiera, specificando in un’intervista rilasciata al Download Festival 2018 che si trattava di un cambio permanente, dato che Van Cleave si era definitivamente risolto a lasciare il gruppo.
Un mese dopo l'uscita dell'album ATW, nel settembre 2018, Parks annunciò che il gruppo avrebbe continuato come trio, senza Draper. ATW fu prodotto dal chitarrista del gruppo, Ben McLeod, e missato dal produttore Rob Schnapf; il risultato fu un album dotato di una musicalità più semplice e naturale rispetto ai precedenti.
La prima uscita del nuovo trio fu il singolo 1X1, distribuito ad Halloween del 2019.
Seguì il sesto album in studio, Nothing as the Ideal, nel settembre 2020. A breve distanza dalla pubblicazione del disco, a metà agosto, il gruppo pubblicò un video musicale per il brano The Marriage of Coyote Woman (lett. "Il matrimonio della donna coyote"). Staebler diresse il video che vedeva egli stesso come protagonista insieme con lo skater professionista Evan Smith. L’album fu registrato presso gli Abbey Road Studios nello Studio Two, già usato da artisti come i Beatles e i Pink Floyd. Nel corso di un’intervista, i componenti del gruppo rivelarono che, malgrado la loro preferenza per le sessioni improvvisate nei garage o per i concerti dal vivo rispetto alle registrazioni in studio, quella registrazione in quel luogo carico di storia li aveva messi subito a loro agio, e che quella si era rivelata l'esperienza migliore che avessero mai fatto in uno studio di registrazione. Della produzione si occupò Mikey Allred, lo stesso di Dying Surfer Meets His Maker.
Ad aprile del 2021, i componenti del gruppo annunciarono sui loro canali social che Van Cleave sarebbe nuovamente tornato a far parte del gruppo, riprendendo il suo ruolo precedente come tastierista. Nel gennaio 2022 pubblicarono una cover di Black Snake di John Lee Hooker. Il gruppo confermò che questa sarebbe stata la prima traccia di Baker’s Dozen, una raccolta di brani che vennero pubblicati a cadenza mensile nel 2022, assieme a una traccia bonus, per un totale di 13 pezzi. Nel marzo 2022, il gruppo pubblicò le registrazioni digitali e le versioni su CD dei loro Live on the Internet, spettacoli in diretta che furono trasmessi nel 2020 durante la pandemia, e resi disponibili in vinile in occasione del Record Store Day del 2021.
Il 24 aprile 2024 Robby Staebler, storico fondatore della band, annunciò di aver lasciato la band per dedicarsi ad altri progetti musicali. Qualche ora più tardi, gli All Them Witches annunciano che per il tour estivo il batterista sarebbe stato sostituito da Christian Powers, già componente e batterista della band Fortune Child.
Il 29 maggio 2026 la band ha pubblicato con la casa dicografica BMG il proprio settimo album in studio, House of Mirrors, con la produzione di Eddie Spear e il nuovo batterista Powers ormai stabilmente in formazione. Il 19 giugno il quartetto così composto ha suonato dal vivo negli studi della radio di Seattle KEXP.
Stati Uniti
