В 1823 г. обозревая местные церкви, епископ Пермский и Екатеринбургский Дионисий заметил, что деревянная церковь на кладбище в городе Перми пришла в ветхое состояние и довел до сведения городского общества, что необходимо заблаговременно предусмотреть надобность в возведении на городском кладбище новой каменной церкви, на что он изъявляет свое пастырское благословение. На заседании городской думы 1 ноября 1823 г. с речью о необходимости строительства новой церкви на кладбище выступил городской голова купец Дмитрий Емельянович Смышляев. Он призвал городское общество собрать деньги для строительства новой церкви. Правивший в то время пермский гражданский губернатор Антон Криденер выразил городской думе свою признательность «за таковой похвальный подвиг». Кроме сбора «доброхотных подаяний», городской думе пришлось заниматься заготовкой кирпичей, для чего на городском выгоне был выстроен кирпичный сарай с обжигательной печью.
Для наблюдения за прочностью и правильностью строения был приглашен известный архитектор Иван Иванович Свиязев.
В 1832 г. состоялась закладка каменной церкви на новом кладбище. В 1837 г. новая церковь была освящена во имя Всех святых. Изящная, круглая в плане церковь с большим куполом, украшенная колоннами, стала одной из архитектурных достопримечательностей губернского города. В новой церкви было два престола: главный, во имя Всех Святых, а второй – во имя Сретения Господня. В 40-х годах общину церкви ликвидировали, а здание церкви изъяли. Но в 1943 г. церковь на новом кладбище уже возобновила свою деятельность.
Здание церкви построено в стиле русского классицизма начала XIX в. в виде ротонды с большим куполом и северным и южным портиками. В 1879 г. с западной стороны был сделан пристрой к притвору храма по проекту чертежника Колесникова, а в 1909 г. по проекту архитектурно-строительного бюро А. Б. Турчевича была выполнена надстройка колокольни.
В настоящее время Всесвятская церковь является действующим храмом Пермской епархии.
