Церковь Михаила Малеина, расположенная у ворот Святотроицкого мужского монастыря, была основана в 1731 году. Изначально на этом месте стоял деревянный храм, который со временем обветшал и был заменен на новый каменный. Важную роль в этом сыграли игумен Макарий и солепромышленник Михаил Турчанинов. Турчанинов планировал построить медеплавильный завод возле Соликамска на речке Талице, земля на которой принадлежала монастырю. В обмен на передачу ему этой земли и мельницы, он обязался построить каменный храм. Строительство началось в 1731 году, и церковь с приделом во имя Петра и Павла была завершена в 1734 году, уже после смерти Турчанинова. Церковь освятили 16 июня того же года.

Новый храм был построен не над воротами, как прежний, а рядом с ними, но сохранил название «надвратный» и стал основанием для колокольни. Архитектурно церковь представляет собой бесстолпный четверик с массивной восьмигранной колокольней. Звонница была устроена над основным храмом, а не над притвором, что выделяет её среди других храмов города. Колокола перенесли со старой деревянной звонницы, но большинство из них расплавилось в пожаре 1743 года. Позже, в 1775 году, звон был усилен за счет колоколов из Пыскорского монастыря, но стены не выдержали нагрузки и треснули. Самый большой колокол так и не подняли, оставив его на земле.

В 1778 году архитектор Василий Кафтырев, изучив состояние церкви, отметил, что колокольня не рассчитана на такой большой звон и предложил её разобрать и построить заново. Однако храм остался стоять и пережил пожар 1806 года. После этого он был закрыт более чем на сорок лет и восстановлен только в 1851 году. В ходе реставрации исчезли первоначальные наличники, замененные на более простые.

Церковь закрыли в 1928 году, уничтожили иконостас, и вместе с монастырем передали Калийтресту, а затем Усольлагу. В 1930 году были разобраны два яруса колокольни и барабан с главкой, а внутреннее пространство разделили на камеры для заключенных.

В 1990-х годах монастырь в Соликамске был восстановлен, и церковь Михаила Малеина вновь стала действующей.