Начало Православия на земле Колымского края было положено в XVII веке русскими землепроходцами ― казаками Москвиным, Дежневым и их сподвижниками; с их приходом стали строиться храмы и часовни. К 1917 году здесь насчитывалось около десяти часовен и церквей, которые впоследствии подверглись поруганию и разрушению.

Возрождение церковной жизни в епархии началось в 1989 году, когда был зарегистрирован первый православный Свято-Покровский приход в Магаданской области. В микрорайоне «Солнечный» приходом был приобретен частный дом, где после переоборудования под молитвенный дом, 21 сентября 1989 г., в праздник Рождества Пресвятой Богородицы, была совершена первая Божественная литургия.

Первоначально приход Покрова Пресвятой Богородицы входил в состав Хабаровской епархии. По мере образования новых приходов на территории обширной Магаданской области, в состав которой входил и Чукотский автономный округ, возникла потребность в образовании самостоятельной епархии. Решением Священного Синода в начале 1991 года приходы на территории Магаданской области были выделены в самостоятельную Магаданскую и Камчатскую епархию.

Первым правящим архиереем Магаданской епархии стал епископ Аркадий (Афонин). В начале своего служения владыка носил титул Магаданского, Камчатского и временно Сахалинского, окормляя огромную территорию, которая потом была разделена на 4 отдельные епархии.

Менее чем за два года был достроен заложенный в 1990 году епископом Хабаровским Гавриилом (Стеблюченко) кафедральный Свято-Духовский собор. Храм был освящен 2 февраля 1992 года, а 15 февраля в нем начались регулярные богослужения.

Рядом с первым магаданским храмом был построен гуманитарный центр с храмом Покрова Пресвятой Богородицы. Было подготовлено и рукоположено несколько священников.

Событием в истории Дальнего Востока стало посещение Магаданской епархии Святейшим Патриархом Алексием II 16-17 сентября 1993 года. В ходе Патриаршего визита в Магадан у соборного храма Святого Духа был отслужен молебен, а также совершена заупокойная лития обо всех невинно убиенных на Колыме ― одной из российских голгоф ХХ века. Святейший Патриарх встречался с руководством области, в муниципальном гуманитарном центре состоялась беседа Его Святейшества с интеллигенцией города Магадана и Магаданской области.

28 ноября 1993 года на Магаданскую кафедру был назначен епископ Ростислав (Девятов). Среди его многочисленных забот о дальнейшем благоустройстве епархии были подготовка и рукоположение новых священнослужителей, открытие приходов, воскресных школ, строительство приходских храмов. Для скорейшего восстановления молитвенной жизни под временные храмы приспосабливались частные дома, общественные помещения.

В 1996 году в центре Магадана в ознаменование 51-й годовщины Победы в Великой Отечественной войне была сооружена и освящена мемориальная часовня в честь великомученика Георгия Победоносца.

В 1999 году продолжались работы по строительству храма Казанской иконы Божией Матери в пос. Снежный и храма Благовещения Пресвятой Богородицы в пос. Синегорье. Попечением правящего архиерея была устроена женская община при Свято-Покровском храме г. Магадана, которая указом Священного Синода от 6 октября 1999 года была преобразована в женский монастырь.

8 октября 2000 года решением Священного Синода управляющим Магаданской и Синегорской епархии (так стала именоваться Магаданская епархия после выделения Чукотки в самостоятельную епархию) определено быть архимандриту Феофану (Ашуркову) с последующим возведением его в сан епископа.

По прибытии на кафедру владыка Феофан начал активную работу по всем направлениям церковной жизни. По его инициативе было положено начало строительства нового величественного Свято-Троицкого кафедрального собора на главной площади города Магадана в октябре 2001 года. Много трудов положил епископ Феофан на улучшение условий церковно-богослужебной жизни колымских приходов. Во многих поселках епархия получила добротные капитальные строения для переоборудования их под православные храмы. Осуществилась разработка проектов реконструкции нескольких молитвенных домов и был заложен первый камень в строительство Свято-Никольского храма 3-го микрорайона г. Магадана. В областном центре при участии всех приходов епархии стали ежегодно проводиться Рождественские чтения. В Магадане и в поселках ― районных центрах стали устраиваться Рождественские елки и Пасхальные концерты для широкой общественности. Было положено начало традиции в день Крещения Господня освящать воду Охотского моря, на берегу которого стоит г. Магадан.

7 мая 2003 г. на Магаданскую кафедру был назначен епископ Гурий (Шалимов). За короткий срок владыка посетил все приходы епархии, где совершал богослужения и общался с местным руководством, паствой и жителями населенных пунктов области. Во время своих поездок по Колыме владыка Гурий особое внимание уделял посещению мест массовых репрессий, где совершались заупокойные службы, устанавливались и освящались поклонные кресты.

14 сентября 2003 г. была совершена первая Божественная литургия в новом строящемся Свято-Троицком кафедральном соборе.