Из Иерусалима с апостолами Петром и Андреем ходил в Антиохию Сирийскую, был в каппадокийском городе Тиане и в Синопе. Здесь апостола Матфия заключили в темницу, из которой он был чудесно освобожден апостолом Андреем Первозванным. После этого апостол Матфий путешествовал в Амасию, город на берегу Понта. Во время 3-го путешествия апостола Андрея святой Матфий был с ним в Едессе и Севастии. По церковному преданию, он был с проповедью в Эфиопии Понтийской (нынешняя Западная Грузия), Македонии, многократно подвергаясь смертельной опасности, но Господь сохранял его живым для дальнейшей проповеди Евангелия. Однажды язычники заставили апостола выпить отравленное питье. Апостол выпил его и не только сам остался невредимым, но исцелил и других узников, ослепших от этого питья. Когда святой Матфий вышел из темницы, язычники тщетно искали его, так как он сделался для них невидимым. В другой раз, когда язычники в ярости бросились, чтобы убить апостола, земля разверзлась и поглотила их. Апостол Матфий вернулся в Иудею и не переставал просвещать своих соотечественников светом учения Христова. Он творил великие чудеса Именем Господа Иисуса и обратил очень многих к вере во Христа. Иудейский первосвященник Анан, ненавидевший Христа, давший ранее повеление сбросить с высоты храма апостола Иакова, брата Господня, приказал взять апостола Матфия и представить на суд синедриона в Иерусалиме. Нечестивый Анан произнес речь, в которой кощунственно хулил Господа. В ответ апостол Матфий показал на пророчествах Ветхого Завета, что Иисус Христос – Истинный Бог, Мессия, обещанный Богом Израилю, Сын Божий, Единосущный и Совечный Богу Отцу. После этих слов апостол Матфий был осужден синедрионом на смерть и побит камнями. Когда святой Матфий был уже мертв, иудеи, скрывая преступление, отсекли ему голову как противнику кесаря. (По некоторым источникам, апостола Матфия распяли на кресте. Некоторые указывают, что он скончался в Колхиде). Смерть за Христа и венец мученика апостол Матфий воспринял около 63 года.