В патриарших окладных книгах от 1626 года написано "Церковь Святых Четыредесят Мученик на посаде… ". В 1652 году построена вторая тёплая церковь в честь Покрова Пресвятой Богородицы для богослужения в холодное время года. В 1728 году вместо старых церквей построены новые деревянные церкви Сорока мучеников Севастийских и Рождества Пресвятой Богородицы.

Кирпичная церковь Сорока мучеников Севастийских в Рыбацкой слободе построена в 1755 году на средства московских купцов Максима и Ивана Щелягиных. Придел тёплый в честь Рождества Пресвятой Богородицы. С 1873 года церковь Сорока мучеников стала приписной к соседней Введенской Церкви. Особого причта при храме Сорока мучеников не было, богослужение и требы отправлял причт Введенской церкви.

В конце 1930-х годов церковь закрыта. Здание храма занято мастерскими, поддерживалась в порядке.

В 1996 году церковь возвращена верующим.