На епархиальном собрании духовенства Камчатской епархии, 9 августа 1999 года, было принято решение о строительстве собора и утверждён проект архитектора Олега Лукомского. В сентябре 2001 года начались строительные работы. В июне 2002 года, в день Святой Троицы, в основание строящегося храма поместили стальную капсулу с мощами святых мучеников Антония, Евстафия и Иоанна и закладную грамоту. Основные работы по строительству были закончены к сентябрю 2010 года. Для росписи собора были приглашены мастера-иконописцы из Волгодонска и Сергиевого Посада. Бригаду иконописцев возглавил член Союза художников России Александр Таничев. Роспись в древнерусском стиле выполнена минеральными красками, что позволяет фрескам сохраняться очень долгое время. Всего расписано было около 200 библейских и евангельских персонажей. Иконографией для монументальных росписей занимался архитектор и иконописец Игорь Мясников. 19 сентября 2010 года патриарх Московский и всея Руси Кирилл совершил освящение собора. При освящении им были дарованы икона святой Матроны Московской и частица её мощей. В 2015 году состоялось освящение придела Артемия Веркольского.
По проекту помещение нижней части храма должно стать концертным залом. Нижний храм будет расписан сценами из истории православия на Камчатке, начиная с первых миссионеров и главных исторических событий Камчатки – прежде всего победой над англо-французской эскадрой в 1854 году. На стенах зала предполагается выполнение росписи всей истории Камчатки.
Вначале строительство велось за счёт пожертвований прихожан, физических лиц, в том числе Владимира Путина и патриарха Алексия II, юридических лиц, благотворительных фондов. Впоследствии финансирование проекта взяла на себя компания «Газпром».
