У исследователей есть сведения о том, что предполагалось назначение Мелхиседека на Казанскую кафедру, однако уполномоченный Совета по делам религии в Татарской АССР выступил категорически против его кандидатуры в связи с активной позицией, занятой Мелхиседеком по вопросу о переносе здания епархиального управления. В августе того же года освобождён от временного управления Казанской епархией. Решением Синода от 3 марта 1976 г. избран в состав Синодальной комиссии по вопросам христианского единства. 9 сентября 1976 г. возведён в сан архиепископа. 10 октября 1978 г. назначен архиепископом Берлинским и Среднеевропейским, Патриаршим экзархом Средней Европы. С 27 апреля 1979 г. по 11 октября 1981 г. Мелхиседек временно управлял Дюссельдорфской епархией; 26 декабря 1984 г. назначен архиепископом Свердловским и Курганским. В том же году стал временно управляющим Челябинской епархией (до 10 апреля 1989 г.). С 25 сентября 1991 г. титуловался Екатеринбургским и Курганским, а с образованием 23 февраля 1993 г. Курганской епархии – Екатеринбургским и Верхотурским. На годы архиерейства Мелхиседека пришлось начало церковного возрождения епархии. Уже в 1988 г. после долгого перерыва было открыто сразу шесть новых приходов, возвращено верующим четыре храма, а количество крещений по сравнению с предыдущим годом увеличилось в три раза. Особенно значимым было возвращение верующим стараниями Мелхиседека екатеринбургских храмов Всех святых и Вознесения Господня, а также закладка в 1992 г. храма-памятника на Крови во имя Всех святых, в земле Российской просиявших, на месте мученической кончины семьи императора Николая II. В 1989 г. по прошению Мелхиседека верующим были возвращены мощи святого праведного Симеона Верхотурского, изъятые из Верхотурского монастыря в 1920 г. В епархии стали создаваться воскресные школы, в частности, школа при Иоанно-Предтеченском соборе в Екатеринбурге, где Мелхиседек сам вёл уроки. Начали издаваться «Екатеринбургские епархиальные ведомости» и «Православный вестник Свердловской епархии». Мелхиседек также участвовал от Московской патриархии в работе комиссии по реабилитации. 28 февраля 1994 г. переведён на вновь образованную Брянскую и Севскую кафедру. При нём в епархии велась активная реставрация храмов и строительство церквей. В 1995 г. в Трубчевске открылись двухгодичные епархиальные пастырские курсы. При храмах епархии были созданы воскресные школы, с 1996 г. действует воскресная школа в брянской детской воспитательно-трудовой колонии. 12–13 марта 2002 г. Священный Синод РПЦ удовлетворил прошение Мелхиседека об увольнении на покой в связи с достижением 75-летия, выразив ему благодарность за понесённые труды. Выйдя на покой, Мелхиседек поселился в городе Климовске (с 2015 г. в черте города Подольска). Мелхиседек был награждён орденами Сергия Радонежского второй степени (1982 г.), святого равноапостольного князя Владимира второй степени (1986 г.), святого благоверного князя Даниила Московского второй степени (1990 г.), медалью святого праведного Симеона Верхотурского первой степени (2012 г.), медалью ордена святого равноапостольного князя Владимира (2015 г.) и золотой медалью «За укрепление мира» (1991 г.). Отпевание Мелхиседека, совершённое 10 июня в Троицком соборе города Подольска Московской области, возглавил Крутицкий и Коломенский митрополит Ювеналий (Поярков). Мелхиседек был погребён у алтаря Воскресенского храма села Молоди.