Церковь во имя Всех Святых (Всехсвятская) – каменная, одноэтажная, однопрестольная. Она была третьей из церквей, заложенных на территории монастыря и второй, освященной в дополнение к Успенской церкви. Она была преобразована из часовни, возникшей на месте захоронения двух почитаемых местными жителями и горожанами блаженных Андрея и Василия, живших в XVIII веке. На ее месте по указу Пермской Консистории 7 августа 1817 г. была заложена, и в 1822 г. освящена (по благословенной грамоте Преосвященного Иустина, епископа Пермского) Всехсвятская церковь.

Согласно описанию Иконникова В., (1875 г.), "кровля храма дугообразна, утверждена на деревянных стропилах и со всех сторон покрыта железными листами, окрашенными зеленой малахитовой краской. Глав на алтаре и церкви две – обе деревянные, шаровидные, обиты белым железом, кресты на них цельные, железные, четвероконечные, окрашенные желтым кроном, а шейки под главами выкрашены белой краской. Алтарь состоит из полукружия, длиной от горнего места до царских врат 5,5 аршин, шириной 5 аршин. В нем три полуциркульные окна. На западной стороне устроены двери, ведущие в полуциркульную, деревянную штукатуренную паперть, а из нее на север идет дверь, ведущая на крыльцо".

В конце XIX века она обветшала и вместе с больничным корпусом, находящимся при ней, была разобрана, а на ее месте в 1900 г. на средства благотворителя, екатеринбургского купца Михаила Ивановича Иванова, было возведено новое здание в кирпичном византийском стиле. По внешнему виду храм мало чем отличался от своих среднеазиатских аналогов. Здания этого стиля сразу легко отличить по характерным признакам поздневизантийского зодчества: двухчастные или трехчастные полуциркульные окна и аркады, плоские купола, кирпичные неоштукатуренные стены.

Здание имело внутри вид креста, было увенчано своеобразным куполом в виде фонаря, не имело колокольни и было соединено с двухэтажным корпусом (с подвальным помещением), на первом этаже которого размещалась богадельня на 80 человек, а на втором этаже была больница на 20 коек. Из каменного корпуса в эту церковь был устроен теплый коридор как с нижнего, так и с верхнего этажей; с верхнего этажа ход вел прямо на хоры, откуда открывался весь внутренний вид храма.

После установления советской власти и закрытия в 1920 г. монастыря эта церковь оказалась в числе первой из закрытых, поскольку она была тесно связана с жилыми помещениями. Внешне здание практически не было изменено, но было лишено крестов, внутреннего убранства и подверглось внутренней перепланировке.

В 2003-2004 гг. монастырем была проведена реставрация храма и части перехода, примыкающей к нему. Здесь устроены подсобные помещения и исповедальня. Выполнены электромонтажные, штукатурные, отделочные работы; осуществлен монтаж отопления; ремонт кровли; укладка полов из керамогранита; установка кованой решетки ограждения хоров, благоустроена территория вокруг храма.

Освящение храма состоялось 2 апреля 2005 года.