В «Хронике» Георгия Синкелла Мельхиседек назван «девственником». Эпизод благословения Мельхиседеком хлебом и вином Авраама из первого славянского перевода «Хроники» Георгия Амартола был включён на Руси в состав Летописца Еллинского и Римского и через его посредство попал в «Русский Хронограф» редакции 1512 г. («Полное собрание русских летописей», том 22, часть 1) и в позднейшие, а также в первый том Лицевого летописного свода, так называемый Музейский сборник (Исторический музей). В сирийском христианском памятнике VI в. «Пещера сокровищ», представляющем собой сборник легендарных сказаний, ошибочно приписываемый в рукописной традиции Ефрему Сирину, Мельхиседек назван сыном Малака из рода Сима. Он играет одну из центральных ролей в сказаниях о патриархах: участвует по поручению Ноя вместе с его сыновьями в похоронах Адама после потопа, молится о Ревекке, предсказывая будущее её сыновьям. Мельхиседек приобщил Авраама на горе Йавос «Святым Таинам, хлебу преложения и вину искупления». На этом месте, именуемом «центр земли», располагался алтарь Мельхиседека; там же была гробница Адама, происходило жертвоприношение Исаака и впоследствии был поставлен крест Христов. Содержащийся в этом источнике рассказ о пророчестве Мельхиседека, обращённом к Ревекке, встречается только в «Христианской топографии» (VI в.) Космы Индикоплова. В гностических текстах из собрания Наг-Хаммади именем Мельхиседека назван апокриф на коптском языке, сохранившийся во фрагментах. В этом тексте апокалиптического характера Мельхиседек представлен как избранный основной носитель тайного откровения от Бога, Его посредник, призванный возвестить народам истину. Мельхиседек играет важнейшую роль в передаче совершаемых посвящёнными молитв к обитателям небесных сфер. В заключение он прославляется как первосвященник Бога Всевышнего, который победил своих врагов – архонтов. В гностическом трактате III в. н.э. «Пистис София» («Pistis Sophia») Мельхиседек именуется «преемником [копт. mparalhmptwr] света» и является важнейшей фигурой гностического мироздания, управляющей архонтами и очищающей получаемую от них силу. В другом гностическом апокрифе – второй «Книге Иеу» содержится молитвенное призывание к Мельхиседеку как к тому, кто приносит воду огненного крещения. Согласно свидетельству Ипполита Римского, существовала гностическая секта, которая почитала Мельхиседека как обладающего превыше всех других сил великой силой и превосходящего Иисуса Христа. Более подробно тему почитания Мельхиседека в гностических кругах рассматривает Епифаний Кипрский, который посвящает Мельхиседеку одну из глав своего сочинения. Он рассказывает о еретиках-мелхиседекианах (др. название – «феодотиане»), почитавших Мельхиседека как некую великую силу, а не простого человека. Истолковывая буквально слова Пс. 109:4, они полагали, что Христос был удостоен чина Мельхиседека, а значит, был меньше последнего и Сам нуждался в нём. Члены секты приносили Мельхиседеку жертвы и обращались к нему в молитвах как к посреднику между ними и Богом. Епифаний Кипрский также сообщает, что вокруг имени Мельхиседека всегда существовало множество ложных представлений. Один египетский ересиарх почитал его за Святого Духа, самаряне считали его Симом, сыном Ноя, иудеи – сыном блудницы и т.д.