Самостоятельный православный приход на Командорских островах был образован в 1887 году. На островах тогда не было храма, но действовало несколько старых обветшавших часовен. Для постройки нового храма, начало которой было намечено на весну 1888 года, был привезён лес из Америки. Строительство церкви продолжалось до 1892 года. На 1892 год приходилась годовщина чудесного избавления от опасности цесаревича Николая, а само село ещё с 1880-х годов называлось Никольским, но старая часовня была освящена в 1842 году епископом Иннокентием (Вениаминовым) во имя святителя Иннокентия Иркутского, который считался небесным покровителем села, поэтому новая церковь была освящена одновременно и во имя Николая Чудотворца, и во имя Иннокентия Иркутского. Несколькими годами позже в селе Преображенском на острове Медный построили ещё одну церковь по проекту Никольско-Иннокентиевского храма. В 1920-х годах оба храма были закрыты. Спасо-Преображенская церковь была разобрана в 1930-х годах. В Никольско-Иннокентиевской церкви разместили сельский клуб, а затем общежитие и художественную школу. В 1983 году здание бывшего храма сгорело.
В 1991 году на Командорских островах были обнаружены останки Витуса Беринга и пяти других участников Второй Камчатской экспедиции. Останки были отправлены в Москву, где после тщательного исследования было решено перезахоронить их на острове Беринга. Для этого на остров прибыл о. Ярослав Левко, который совершил панихиду по погибшим морякам. Это была первая церковная служба на острове с 1926 года. В 2009 году в Министерстве юстиции была зарегистрирована местная православная община. Приступили к вопросам постройки храма.
17 сентября 2010 года патриарх Кирилл посетил Командорские острова и освятил место строительства нового храма. Ровно через год было освящено основание церкви, а 3 ноября 2011 года на остров доставлен разобранный храм. Из Кирова до Владивостока его везли на железной дороге. Вятские мастера восемь недель собирали храм на месте. В сентябре 2012 года в церкви установили иконостас, сделанный художниками мастерской «Абрамцево» из Сергиева Посада. Алеутский краеведческий музей вернул колокол Никольско-Иннокентиевской церкви, вылитый в 1891 году в Санкт-Петербурге на заводе В. Орлова. 27 октября 2012 года епископ Петропавловский и Камчатский Артемий совершил освящение храма.
