До того как стать учеником Иисуса, Андрей состоял среди последователей Иоанна Крестителя. По свидетельству Евангелия от Иоанна, он был первым призван на апостольское служение. Поэтому в греческом предании он носит имя «Первозванного». После смерти, воскрешения и вознесения Иисуса Христа, Андрей, прияв вместе с прочими апостолами Св. Духа, отправился проповедовать слово Божие. По жребию он получил в удел малоазиатскую область Вифинию, земли, омываемые Чёрным морем, а также римские провинции на Балканском полуострове (Фракию, Македонию, Фессалию и Ахаю).

Андрей первым проповедал Христово учение в Византии (будущем Константинополе), многих обратил в новую веру и поставил византийским епископом того Стахия, о котором апостол Павел упоминает в своём Послании к римлянам (Рим. 16: 9). Продолжая свои труды, Андрей отправился вокруг Чёрного моря, побывал в Грузии, Армении, пересёк Кавказские горы и из Севастии по берегу достиг Тавриды. (По позднейшим русским преданиям, апостол добирался вверх по Днепру до самых Киевских гор.) Проповедав христианство «скифам» (то есть народам, жившим на южных, восточных и северо-восточных берегах Чёрного моря), Андрей перешёл во Фракию и Грецию.

В ходе своих апостольских странствий Андрей претерпел немало скорбей и страданий. Так в Синопе противники Христовой веры, распростёрши его по земле, влачили за руки и ноги, били палками, бросали в него камнями, вырывали зубы и пальцы, так что он едва остался в живых. В конце концов апостол добрался до Пелопоннеса и остановился в Ахайском городе Патрах у некоего благочестивого мужа по имени Сосий. Многие из местных жителей вскоре приняли новое учение. Жена проконсула Егеата Максимилла, получив от Андрея исцеление, также уверовала во Христа. Но сам проконсул, видя такие успехи проповеди Андрея, разгневался до неистовства. Он велел схватить апостола и распять его на кресте. Приказание было исполнено в точности. Считается, что мученическая кончина апостола последовала в 80 г. Позднейшее предание сообщает, что Андрей принял смерть на кресте, поперечные брусья которого были сбиты наискось (так называемый Андреевский крест).