В 1875 г. "стараниями жен и финансами мужей семейства Курлиных, Головкиных, Тимрот и других известных людей города" было учреждено "Общество попечительства о бедных", которое, в свою очередь, открыло в 1878 г. приют для детей-сирот воинов, погибших, сражаясь в Самарском ополчении под Самарским Знаменем за освобождение болгарского народа от турецкого ига. Приют получил наименование "Мариинский" в память усопшей императрицы-матери Марии Федоровны. В заведение принимались девочки в возрасте от 5 до 12 лет и содержались до 17 лет. Приют располагался на Саратовской (Фрунзе) улице в двухэтажном доме, подаренном потомственным почетным гражданином Ильей Даниловичем Ковригиным. Первоначально своей церкви в приюте не было, и воспитанницы посещали Покровскую церковь. В начале 90-х гг. XIX в. попечительница приюта вдова коллежского асессора Надежда Илларионовна Шехларева приобрела примыкающий к территории участок земли, площадью 480 кв. саженей (16 саженей в ширину и 30 саженей вглубь), выходящий одной стороной на ул. Николаевскую (ул. Чапаевская, 136). На этом участке на ее средства в 1896 г. началось строительство домового храма. 15 ноября 1898 г. храм был освящен.
Проект церкви в русском стиле разработал самарский архитектор А.А. Щербачев. Строительство храма вел Гласный Самарской городской думы, депутат Государственной думы России, страстный борец за трезвый образ жизни, купец-крестьянин и староста храма Михаил Дмитриевич Челышев. Церковь имела два придела: во имя святителя Христова Николая и во имя святых мучениц Веры, Надежды, Любови и матери их Софии.
В 1918 г. Мариинский приют был закрыт, а храм святых мучениц Веры, Надежды, Любови и Софии продолжал богослужения как приходская церковь до 15 октября 1929 г., когда решением Самарского горсовета приход был закрыт. В январе 1930 г. горсовет принял решение об открытии в здании церкви музея революции. В ходе работ по приспособлению здания под музей были сняты маковки, разобраны верхние ярусы колокольни, в основном объеме церкви были сделаны межэтажные перекрытия.
Постановлением Главы администрации Самарской области от 22 ноября 1991 г. здание церкви возвращается православным верующим. Начались ремонтно-восстановительные, а затем и реставрационные работы храма святых мучениц Веры, Надежды, Любови и матери их Софии. Первое богослужение было проведено 29 сентября 1994 г. в праздник святых мучениц Веры, Надежды, Любови и матери их Софии. В год столетнего юбилея храма 13 декабря 1998 г. на праздничной литургии Высокопреосвященнейший архиепископ Самарский и Сызранский Сергий совершил чин освящения престола храма во имя святых мучениц Веры, Надежды, Любови и матери их Софии.