В средневизантийское время изображение Мельхиседека вводится в Псалтирь так называемого монастырского типа в качестве иллюстрации к Пс. 109:4. В центре композиции Иисус Христос причащает апостолов, по сторонам – царь Давид и Мельхиседек: миниатюры в Хлудовской Псалтири (Исторический музей, середина IX в.); в Лондонской Псалтири (1066 г.); в Псалтири Барберини (третья четверть XI в.). В более позднее время вместо развёрнутой композиции «Евхаристия» появляется сокращённый вариант, где представлен лишь Мельхиседек (Киевская Псалтирь – Российская национальная библиотека, 1397 г.). В монументальных циклах в средневизантийский период образ Мельхиседека нередко является парным образу Авраама (например, в медальоне верхнего яруса на северной стене пресбитерия в кафедральном соборе в Чефалу, Сицилия, 1166 г.; на склоне вимы в мозаиках собора Святой Софии в Киеве, 1040 гг.; на фреске алтарной арки Спасо-Преображенского собора Мирожского монастыря в Пскове (рубеж 1130 и 1140 гг.). В дальнейшем в программе росписи храмов изображение Мельхиседека отдельное или в сценах с Авраамом рассматривается как прообраз Христа (например, на мозаике северного купола Сан-Марко в Венеции, XIII в.; в росписях северного купола нартекса монастыря Хора (Кахрие-джами) в Константинополе, около 1316 – 1321 гг.; Успенского собора Протата, Карея, на Афоне, мастер Мануил Панселин, 1316–1321 гг.; Успенской церкви монастыря Грачаница, мастер Михаил Астрапа, 1320–1321 гг.). В русских, преимущественно новгородских, росписях изображение Мельхиседека почти всегда помещается в паре с Аароном или Захарией на предалтарной арке (например, в Великом Новгороде в церкви Успения на Волотовом поле, 1363 г.; в церкви великомученика Феодора Стратилата на Ручью, 1380–1390 гг.; в церкви архангела Михаила Сковородского монастыря, начало XV в.; в церкви святого Симеона Богоприимца Зверина монастыря, конец 1460 – начало 1470 гг.; в церкви Спаса Преображения на Ильине ул., мастер Феофан Грек, 1378 г., – образ Мельхиседека помещён в простенках окон барабана вместе с праотцами, с пророком Илиёй и с Иоанном Предтечей). На фресках собора Рождества Пресвятой Богородицы Ферапонтова монастыря (1502 г., мастер Дионисий) Мельхиседек представлен дважды: в барабане в цикле праотцев и на предалтарной арке в паре с Аароном; в Благовещенском соборе Московского Кремля (1547–1551 гг.) – между окнами центральной главы. В иконописи до появления русского высокого иконостаса образ Мельхиседека встречается исключительно редко (например, на синайской иконе «Авраам и Мелхиседек, с ктитором»; исследователям известна по фотографии из коллекции Принстонского университета, США).