В 1830 году архимандрит Макарий (Глухарёв), основатель Алтайской духовной миссии, прибыл на Алтай с целью распространения христианства среди местного населения. Первоначально он обосновался в Улале (ныне Горно-Алтайск), однако в 1831 году, столкнувшись с сопротивлением местных жителей, переехал в Майму, где снял жильё у крещёного инородца С.Е. Чендекова. В 1832 году началось строительство первого миссионерского дома, завершившееся в 1835 году. Согласно некоторым источникам, этот дом располагался на левом берегу реки Майма, недалеко от Катуни.
В 1842 году архимандрит Макарий инициировал строительство каменного храма для миссии. Главным благотворителем выступил томский купец Михаил Евфимьевич Шебалин, а проект разработал томский архитектор Алексей Алексеевич Арефьев. Закладка храма состоялась 4 июня 1845 года под руководством протоиерея Стефана Ландышева, начальника миссии. Строительство было завершено в кратчайшие сроки, и уже 30 августа 1845 года епископ Томский и Енисейский Афанасий (Соколов) освятил однопрестольный каменный храм с колокольней в честь Сошествия Святого Духа на Апостолов.
Первоначально храм имел форму, близкую к базилике. В 1882 году, на средства местного жителя, торгующего инородца Андрея Семёновича Сафронова, церковь была расширена двумя каменными пристроями с северной и южной сторон, что значительно увеличило её вместимость.
В 1848 году, в связи с увеличением числа крещёных инородцев, храм был преобразован в приходской, став первым православным приходом в Горном Алтае. Настоятель прихода обязан был иметь особое попечение о новокрещённых, живущих в этом приходе, и исполнять у них все требы безвозмездно. С 22 декабря 1855 года по март 1858 года настоятелем майминской церкви был священник-миссионер Василий Иванович Вербицкий, известный как этнограф, лингвист и фольклорист.
В советский период, в 1938 году, храм был закрыт. Сначала в его стенах разместили клуб, а после войны — агрохимлабораторию, для нужд которой здание было перестроено: добавлен второй этаж и гараж.
В 1996 году здание храма было возвращено Русской Православной Церкви. После проведения восстановительных работ, 8 января 1997 года, в храме состоялась первая после долгого перерыва Божественная литургия. В 2005 году завершилась реконструкция внутреннего помещения, и 22 октября того же года храм был освящён епископом Барнаульским и Алтайским Максимом.