Frelsens Hær blev stiftet af en metodistpræst, som hed William Booth. Som 17-årig begyndte han at arbejde som gadeprædikant, og det var der igennem, han mødte sin kone Cathrine Mumford, og sammen tog de sig af de fattige. Som tiden gik, syntes de, at det var for lidt plads i deres eget sogn, og de mente heller ikke, at metodismen var helt på den rigtige måde. Derfor droppede de metodismen og blev selvstændige. Nu kunne han for alvor sprede sit syn på Gud over hele landet.

I 1865 begyndte Cathrine og William igen at koncentrere sig om de fattige i London, hvor de gik under navnet "The East London Revival Society". De prøvede på at forbedre slumkvarternes vilkår, og deres arbejde spredte sig meget hurtigt til resten af landet. Det, som de gik mest ind for, var ligestilling, og et af deres mottoer var, at alle mennesker skulle have det lige så godt som en drosselhest. De hjalp altid andre, både med bespisning og indsamling af tøj til de fattige og meget andet.

Da de havde en ret så stor fremgang, skulle de til at finde ud af, hvordan den Kristne Mission, som de kaldte sig selv, skulle tilrettelægges - hvad slags kirke, det skulle være og vigtigst af alt, hvilken trosretning de ville tilhøre. Egentlig var det kun meningen, at den Kristne Mission skulle få fat i folk og så sende dem over i kirken bagefter. De syntes bare ikke, at de folk, de fik fat i, passede særlig godt til kirken, så de ville opfinde en ny trosretning. Da Booth var tidligere metodistpræst, var det naturligt for ham at følge metodismens love. Imidlertid var der stor uenighed om, hvad de skulle vælge, og hvad den skulle indebære: om der skulle være vand eller vin i kanden, om kvinder også måtte uddele sakramenter, hvilke sakramenter skulle der være og meget andet. Men langt om længe kom den til at hedde "Frelsens Hær" i stedet for Kristen Mission, fordi de mente, at de var som en Hær, der kæmpede for menneskelige vilkår.

Da Frelsens Hær ikke var statsejet, skulle de selv skaffe penge til lønninger. En af måderne, de kunne få økonomisk hjælp på, var at tage ud at synge og spille på gaderne. Sang og musik spiller en meget vigtig rolle for alle, der er medlem af Frelsens Hær - ikke bare som lovsang, men også som en slags "forkyndelse". Et af deres logoer er og var "blod og ild". Blodet står for Jesu blod, og ilden står for Helligånden. Det er det logo, de har på deres uniformer og deres skilte. Deres farver er rød, gul og blå, men de har også en masse andre farver, som de bruger i andre forbindelser. Alle de farver de har, har for det meste noget med at gøre med alle de forskellige hudfarver i verden.