Возведение церкви Всех Святых на Егошихинском кладбище, как и возникновение самого кладбища следует отнести ко времени открытия Пермского наместничества и основания в 1781 году на месте поселка медеплавильного Егошихинского завода губернского города Перми. Кладбище расположилось на горе, между рекою Егошихою и впадающим в нее ручьем Стиксом.
В 80-х годах XVIII столетия на Егошихинском кладбище началось строительство скромной деревянной церкви в честь Всех Святых. В декабре 1783 г. губернатор Пермского наместничества Евгений Петрович Кашкин отдал в приказ общественного призрения распоряжение «о построении близ города Перми церкви для погребения умерших» с предложением произвести сбор средств на богоугодное дело. Деньги для строительства храма охотно жертвовали владельцы частных заводов, купцы, мещане и простые жители Перми. Благодаря такому усердию деревянную церковь построили быстро, и 10 декабря 1784 года священник Петропавловского собора Антоний Попов освятил новый храм в честь Всех Святых. При кладбищенской церкви находилось деревянное здание богадельни, которая содержалась на средства приказа общественного призрения. Всехсвятский храм в то время не имел собственного причта и был приписан к Петропавловскому собору.
Но не прошло и полувека, как деревянная церковь Всех Святых утратила свой благолепный вид. В 1823 году вновь возведенный на Пермскую кафедру епископ Дионисий (Цветаев), обозревая храмы Перми, обратил внимание на необычайную ветхость кладбищенского храма. Он довел до сведения городского общества о необходимости возведения на городском кладбище новой каменной церкви, и дал на то свое архипастырское благословение. Предложение вновь было поддержано городским обществом, и опять купцы и мещане города Перми стали собирать деньги на строительство новой церкви. Для наблюдения за прочностью и правильностью строения был приглашен известный архитектор Иван Иванович Свиязев. Однако, к возведению храма не приступали несколько лет.
В сентябре 1824 года Губернский город Пермь посетил Император Александр I. Обозревая казенные и общественные учреждения города, Государь осмотрел старую деревянную церковь Всех Святых, богадельню приказа общественного призрения на Егошихинском кладбище. Известно, что Монарх не раз делал выговоры местным чиновникам относительно обнаруженных им недостатков городского быта. Вероятно, ветхость и запущенность деревянного кладбищенского храма вызвали его неудовольствие. Губернатор Пермского наместничества Кирилл Яковлевич Тюфяев и купец 1-й гильдии, занимавший пост пермского городского головы Дмитрий Емельянович Смышляев сообщили Государю о том, что еще в 1823 году Мещанское общество приняло решение о строительстве на кладбище новой каменной церкви. Они выразили верноподданническое желание возвести храм «…с хвалой Всевышнего творца и за здравие Всеавгустейшего Государя Александра Павловича и всей Его Царской фамилии».
Обещание, данное Императору, долгое время оставалось неисполненным. В 1831 году новый Губернатор Пермского наместничества Гавриил Корнеевич Селастенник недоумевал, почему до сих пор градское общество не приступило к возведению Всехсвятской церкви. Выяснилось, что собранные деньги были потрачены думой на городские нужды: для строительства полицейских будок, устройства торговых лавок и столбов с фонарями.
Тем временем Егошихинское кладбище в Перми значительно увеличилось. Погост был разделен на несколько участков. Древняя часть кладбища стала называться «Старым кладбищем». Чаще всего захоронения стали совершать в той части, за которой закрепилось название «Новое кладбище». И вот, 30 мая 1832 года архиепископ Пермский и Екатеринбургский Аркадий (Федоров) освятил место, отведенное для строительства Всехсвятской церкви, но уже на Новом городском кладбище. После закладки каменной церкви старинная Старокладбищенская церковь была переименована в Успенскую. В 1838 году тщанием коммерции советника Дмитрия Емельяновича Смышляева церковь на Новом кладбище по проекту архитектора Иван Ивановича Свиязева была построена. 13 ноября храм был освещен архиепископом Пермским и Верхотурским Аркадием. В нем устроено два престола: главный, во имя Всех Святых, и придел на хорах – во имя Сретения Господня.
Здание церкви решено в стиле русского классицизма начала XIX века – в виде ротонды, что является чрезвычайно редким приемом в русском церковном строительстве. Изящная, круглая в плане церковь, с большим куполом, украшенная колоннами, является одной из архитектурных достопримечательностей губернского города и представляет уникальный памятник архитектуры. В народе церковь Всех Святых стала именоваться «Новокладбищенской».
Долгое время Смышляев-старший оставался попечителем Всехсвятского храма, обеспечивая его всем необходимым. Еще при жизни Дмитрий Емельяновича в алтарной части была устроена фамильная усыпальница для захоронения членов его семьи. После кончины, последовавшей в 1857 году, боголюбивый меценат был похоронен под алтарем Всехсвятской церкви.
В Пермском крае Дмитрий Емельянович Смышляев известен те только как строитель и попечитель храма Всех Святых, но и как отец известного общественного деятеля, первого председателя губернской земской управы, историка-краеведа Дмитрия Дмириевича Смышляева.
На время покинув Пермь, Смышляев-младший с 6 ноября 1885 по 21 августа 1889 года трудился в Палестине в качестве первого уполномоченного Императорского Православного Палестинского общества. Находясь на Святой Земле, Дмитрий Дмитриевич возложил на себя почти непосильный труд, руководя строительством двух главных русских объектов: Нового (Сергиевского) подворья и Русского Дома у Порога Судных Врат (будущего Александровского подворья с храмом святого князя Александра Невского). Известно, что во Святой Земле близким другом Смышляева стал его земляк – начальник Русской Духовной Миссии архимандрит Антонин (Капустин).
За свою деятельность в Палестине Дмитрий Дмитриевич Смышляев удостоился звания почетного члена Императорского Православного Палестинского общества, а так же стал кавалером ордена Гроба Господня.
Возвратившись в Пермь, он исполнял должность секретаря Губернского Статистического Комитета, продолжая при этом краеведческие занятия. Умер Дмитрий Дмитриевич Смышляев 15 ноября 1893 года и был похоронен рядом с отцом, в храме Всех Святых на Новом кладбище. Согласно его духовному завещанию, в дар Всехсвятской церкви была передана икона Воскресения Господня, которую он привез из Иерусалима. Икона была написана на доске от купола Кувуклии Гроба Господня, в нее вложена подлинная частица от камня Святого Гроба.
В июле 1852 года, когда храмовый комплекс и Новое городское кладбище были окончательно благоустроены, епископ Пермский и Верхотурский Неофит (Соснин) принял решение образовать при Всехсвятский Новокладбищенской церкви самостоятельный приход.
В 1879 году Всехсвятский храм претерпел архитектурные изменения: его строгий классический стиль частично сменило причудливое сочетание византийских и античных элементов зодчества. В январе 1895 году при Всехсвятской церкви была открыта женская школа грамоты.
В начале XX века вновь начались работы по реконструкции храма Всех Святых. Помещение притвора было разделено горизонтальным деревянным перекрытием, образовавшим под Сретенским приделом еще одно помещение. Фасад каменной колокольни был украшен ложными двойными колоннами и ажурными коваными оградами обеих звонниц. Постройку венчала полукруглая главка с карнизами и небольшим восьмиконечным крестом. Храм стал выглядеть более внушительно, его силуэт приобрел более четкие очертания, цельность и уравновешенность.
После революционного переворота 1917 года во Всехсвятской Новокладбищенской церкви продолжали совершаться богослужения. 1941 году Молотовский горисполком принял решение о закрытии храма. Но в 1942 году церковь на Новом кладбище была вновь возвращена верующим. К тому времени Всехсвятский храм потерял свое былое величие: кирпичная кладка была повреждена, здание имело четыре сквозных трещины, ветхая железная крыша местами протекала. Роспись храма была замазана масляной краской, утрачен иконостас. В этот период церковь Всех Святых являлась единственной действующей в городе Перми.
С октября 1943 года храм был временно объявлен Кафедральным собором Молотовской (Пермской) епархии. С этого времени и до 25 мая 1944 года в нем служил вернувшийся из ссылки епископ Молотовский и Соликамский Александр (Толстопятов).
В годы Великой Отечественной войны духовенство и прихожане Всехсвятской Новокладбищенской церкви собирали щедрые пожертвования в Фонд обороны страны. Уполномоченный Совета по делам Русской Православной Церкви по Молотовской области П. И. Смирнов докладывал руководству: «В 1943 года Кладбищенская церковь внесла около миллиона рублей…». 23 августа 1943 года на имя настоятеля храма Всех Святых протоиерея Иоанна Караваева и председателя церковно-приходского совета Я. Г. Махнева поступила телеграмма Верховного Главнокомандующего Иосифа Сталина: «Прошу передать духовенству и верующим Молотовской Новокладбищенской церкви, собравшим 302 400 рублей на строительство танковой колонны «Дмитрия Донского» и 582000 рублей на оборону и подарки красным бойцам мой братский привет и благодарность Красной Армии».
В советские годы храм Всех Святых в воскресные и праздничные дни был переполнен молящимися. На службы сюда приходило от трехсот до шестисот человек. В храме был собран великолепный хор, в котором пело до 30 певчих.
В 1989 году при Всехсвятской церкви было построено два новых здания – воскресная школа и дом настоятеля.
В период с 2003 по 2012 годы в Новокладбищенском храме был проведен капитальный ремонт: деревянные конструкции заменены бетонными, устранены трещины купола и стен, крыша покрыта цинком, пол – разноцветным гранитом. Установленный еще в 1946 году фанерный иконостас заменен на новый, выполненный Екатеринбургскими мастерами.
Приход Всехсвятского храма города Перми активно занимается просветительскй и миссионерской деятельностью.