Завязкой «Андрея и Матфия деяний» является захват апостола Матфия (в некоторых вариантах Матфея) людоедами, в городе которых он проповедовал. На тридцатый день они собирались съесть апостола вместе с другими пленниками. Об этом за три дня до назначенной казни сообщил апостолу Андрею, проповедовавшему в Ахее (во второй редакции – в Амасии), Сам Христос, призвавший апостола отправиться на помощь собрату. Андрей с учениками сел на корабль, которым управлял Христос в виде кормчего и два ангела в обличье моряков. Не узнав корабельщиков, апостол вместо платы за проезд рассказывает им об Иисусе; материал этих рассказов почерпнут как из канонических Евангелий, так и из апокрифов. После высадки у города антропофагов (с этого момента вторая редакция, излагающая путешествие по морю пространней, совпадает с первой) апостол Андрей, освободив Матфия и других пленников и вернув им зрение и разум, вывел их за стены, а сам вернулся в город. После многих перипетий и мучений он, вызвав потоп, обратил людоедов ко Христу, после чего покинул их. Вторая редакция добавляет рассказ о возвращении Андрея в город и его дальнейших проповедях. Название города людоедов в тексте первой редакции не сохранилось, однако оно есть во второй редакции, а также в «Мученичестве Матфия» и в латинских переработках «Андрея и Матфия деяний» и читается как Мирна, Мирмена или Мирмидона. А. фон Гутшмид попытался (на основе созвучия) идентифицировать этот город с боспорским Мирмекеем, а людоедов отождествить со скифами, среди которых, согласно восходящей к Оригену традиции, проповедовал апостол Андрей. Очень рано этот город начинают локализовать где-то на южном берегу Чёрного моря: согласно исследованиям М. ван Эсбрука, некоторые восточные памятники идентифицируют его с Мармаридием (около Амасии); апостольские списки помещают его в Иссулимене (устье Чороха); наконец, не позднее VI в. основным становится отождествление его с Синопой (Паломничество Феодосия). Материал «Андрея и Матфия деяний» был использован также в более поздних Житиях Андрея (Епифания Монаха, «Narratio» и др.), причём подвергся серьёзной переработке: Епифаний, например, разделил «Андрея и Матфия деяния» на две части, а людоедов отождествил с иудеями. В славянской традиции известны с XIV–XV вв. «Андрея и Матфия деяния» (например, Исторического музея), ни по языку, ни по бытованию в рукописях не имеющие ничего общего с переводом «Петра и Андрея деяний» (сохранились тексты с XII в.), но связанные с неопубликованным переводом первой редакции Жития Епифания Монаха, что отражает архаическую стадию греческой традиции.