Ontstaan
Het nummer is gebaseerd op een sample uit Insomnia van Faithless. Het is niet de eerste keer dat Rexha met de Faithless werkt: eerder verscheen al Dollars and Dimes, op het Faithless-album Champion Sound. Volgens Rexha gaat "New Religion" over "loslaten en opgaan in de muziek". Op Instagram vertelde ze hoe het nummer tot stand kwam: "Ik zat in een donkere periode. Ik was gefrustreerd, boos… en echt depressief. Het voelde alsof ik in een kooi zat en hoe hard ik ook schreeuwde, ik kwam er niet uit. Dus ging ik terug naar het enige dat me altijd iets laat voelen: dancemuziek". Dus zocht ze haar vlucht in het uitgaan. Ze voegde eraan toe: "Wanneer de bas door je borst dreunt en je jezelf verliest in de muziek, doet niets anders er nog toe. Daar voelde ik me weer vrij. 'New Religion' is mijn liefdesbrief aan muziek". Ook zei ze dat het nummer gaat over "je veilig voelen in de muziek en die energie opnieuw ervaren. Ik hoop dat wanneer mensen het horen, ze willen opstaan en dansen, maar nog meer hoop ik dat het ze het gevoel geeft dat ze leven".
Rexha wilde "Insomnia" aanvankelijk alleen gebruiken als basis voor "New Religion", maar de overgebleven leden van Faithless vonden Rexha's nummer zo goed dat ze meteen hun naam aan de credits toe wilden voegen. De zangeres sprak haar dankbaarheid uit aan Faithless voor het feit dat ze elementen uit hun originele nummer mocht gebruiken. "Dat betekent meer voor me dan je weet". Ze leerde de Faithless-leden Sister Bliss en Rollo persoonlijk kennen.
Het nummer werd als single gekozen door fans van Rexha, die op basis van fragmenten van alle liedjes van het nieuwe album hun stem konden uitbrengen. Rexha kende het origineel van Faithless uit haar jeugd via haar oom, die bijkluste als dj. "Hij liet me kennismaken met allemaal coole danceplaten die je in de Verenigde Staten niet op de radio hoorde".
Hitsucces
"New Religion" flopte in Rexha's thuisland Amerika, waar de Billboard Hot 100 niet werd gehaald. Wel bereikte het de 12e positie in de Digital Song Sales-lijst van Billboard. In het Verenigd Koninkrijk, het thuisland van Faithless, werd de plaat een bescheiden hit en bereikte het de 41e positie. Op het Europese vasteland leverde het nummer Rexha en Faithless daarentegen een enorme hit op, ook in het Nederlandse taalgebied. Zo werd het nummer Alarmschijf op Qmusic, en Dancesmash op Radio 538. Het nummer bereikte de 6e positie in de Nederlandse Top 40. Ook in de Vlaamse Ultratop 50 kende de plaat succes, daar bereikte het de 12e positie. Hiermee bracht Rexha Faithless na bijna 22 jaar weer terug in de Nederlandse Top 40, en na bijna 16 jaar weer in de Vlaamse Ultratop 50.
