В этом тексте повествуется о том, что Матфий проводит три года в тюрьме в Бартосе, который исследователи отождествляют то с Тартусом, то с Парфией. Христос посылает туда Богоматерь, Она освобождает Матфия и других узников и совершает множество чудес. В конце рассказа бежавший из города Матфий возвращается туда на чудесном облаке. Исследователи полагают, что хотя город людоедов нигде в текстах прямо не связывается с Эфиопией, «экзотический» антураж повествования способствовал появлению такой идентификации, которая, вероятно, восходит к тексту параграфа об апостоле Андрее в cписке апостолов Псевдо-Епифания (V–VI вв.), в котором даётся описание местности, «где лагерь Апсар, Иссулимен и река Фасис, где живут эфиопы (в некоторых рукопиcях – «внешние эфиопы»). Уже в параграфе о Матфии того же списка говорится о его мученической смерти от эфиопов во внешней Эфиопии, в порте Иссулимен. Предание о мученической смерти Матфия в Эфиопии исследователи встречают затем в списке апостолов Абу-ль-Бараката и в «Церковной истории» Никифора Каллиста Ксанфопула. По списку апостолов Псевдо-Дорофея (конец VIII в.), Матфий проповедовал в Эфиопии, но распят был в Британии, что исследователи объясняют смешением с соседним параграфом об апостола Симоне Зилоте. Другие апостольские списки содержат иные версии проповеди и кончины Матфия. В списке апостолов Псевдо-Ипполита (VII–VIII вв.) говорится о благовестии Матфию в Иудее, его мирном преставлении там и о погребении в Иерусалиме. Согласно первому сирийскому типу комплексных списков, Матфий происходил из колена Рувимова; некторые списки содержат сообщение о его проповеди в Элладе и на Сицилии (в одном добавлены Агригент, Фессалоника и Ирландия), где он преставился и был погребён. В списках второго сирийского типа упоминаются проповедь Матфия в Иудее и неким респотациям (respotacii) и кончина в Бейруте. В средневизантийский период важнейшей новацией становится превращение Матфия в «Житии апостола Андрея», составленном Епифанием Монахом, в постоянного спутника апостола Андрея. Согласно Житию, Матфий последовал за апостолами Петром и Андреем на проповедь в Антиохию, Тиану, Анкиру и Синопу, где иудеи схватили Матфия и заключили в тюрьму на три дня. Апостол Андрей освободил Матфия и семь дней прятал его и других узников в пещере на берегу моря, а затем отправился с Матфием на восток, в Амис, Трапезунд, Лазик, Иверию, Парфию и, наконец, в Иерусалим. После праздника Пятидесятницы Матфий пришёл с апостолами Петром, Андреем, Иоанном Богословом, Филиппом и Варфоломеем в Антиохию, а оттуда вместе с апостолом Андреем – в миссионерское путешествие. К празднику Пятидесятницы они вернулись в Иерусалим, а затем Матфий с апостолами Андреем, Симоном и Фаддеем направился в Эдессу, а оттуда, без Фаддея, – на Кавказ. После посещения сванов и крепости Химар (по мнению исследователей, в верховьях реки Кодори) «в этих странах остался Матфий с учениками, творя множество чудес». Версию Епифания Монаха повторяют Никита Давид Пафлагон и Симеон Метафраст. В зависящем от Епифания Монаха списке апостолов из анонимного апокрифического «Жития апостола Андрея» Матфию достаётся удел «от Виза́нтия – Понт, Фригия, Памфилия, Армения, Харсиан и до людоедов». Мощи Матфия хранятся в церкви Санта-Мария-Маджоре в Риме и в Трирском соборе. На Западе Матфий считался покровителем мясников.