По вознесении Иисуса Христа на небо, получив обещанного Утешителя, Духа Святого, апостолы, сообразно повелению своего Господа, должны были проповедовать евангелие всей твари.
Древнее предание говорит, что, пред расселением из Иерусалима, все они соединились в последний раз в одной пещере и там, по внушению Духа Божия, составили так называемый апостольский символ веры, как план будущей всемирной проповеди, и что при этом, как некогда израильтяне при наследовании обетованной земли, по жребию разделили между собою вселенную. Жребием св. апостола Андрея были обширные страны Вифинии и Пропонтиды, Греции и Македонии, Фракии и Скифии.
Поморье древнего Евксинского Понта было первым поприщем апостольского служения св. Андрея между язычниками. Он прошел его во всю длину, от Трапезунда и Синопа до Византии, посетил Неокесарию, Самосаты и множество других городов, всюду благовествуя Христа и насаждая церкви. Часто апостольские труды его вознаграждаемы были ужасными страданиями: в Синопе язычники, раздраженные смелым обличением идолослужения, подвергли апостола тяжким мучениям, и едва не лишили его жизни, но благодать Божия чудесно сохранила его для благовествования евангелия другим странам, а верные ученики проводили его до Херсона. Основав здесь Церковь, св. Андрей решился предпринять новое апостольское путешествие. Доселе он проповедовал И. Христа просвещенным народам древнего мира, теперь пред ним открыты были обширные страны, занимаемые дикими воинственными племенами, чуждыми гражданской образованности, - одним словом, те непроходимые пустыни Скифии, во глубь которых не дерзали проникать и самые завоеватели. Но ни трудность подвига, ни опасности, которые угрожали в этих странах, не могли устрашить Первозванного апостола Христова. Сопутствуемый несколькими учениками, он отплыл из Херсона вверх по Днепру, и пустыни Скифии услышали в первый раз имя Христово. Тогда-то, по сказанию Нестора, св. Андрей, плывя мимо гор, на которых впоследствии был построен Киев, "возлюби место". Прекрасное местоположение, высокие горы и обширный вид, открывающийся с них на окрестные страны, привлекли внимание апостола. Он вышел из ладии своей на берег, светлый взор его сквозь мрак времен отдаленных провидел будущее величие христианской России; и он, проникнутый Духом Божиим, благословил священные холмы Киева, водрузил на одном из них крест, и, обратясь к ученикам своим, сказал: "На сих горах возсияет благодать Божия, и град велик имать быти и церкви многи имать Бог воздвигнути..." Через 12 веков потом, в память славного пророчества, сооружена была на сем месте церковь во имя Воздвижения Честного Креста, замененная в половине прошедшего столетия великолепным храмом, воздвигнутым достойною дщерию Петра Великого в честь самого Первозванного апостола. Предание говорит, что св. апостол не ограничился благовествованием евангелия одним только южным странам нынешней России, но что он простер победное слово свое до самых берегов озера Ильменя. Благовестив таким образом слово Божие последним концам тогда известного мира, апостол, по преданию, был потом в Риме, был также в Византии, где поставил первого ее епископа Стахия.
Ни лета, ни тяжкие подвиги апостольства не погасили в св. Андрее ревности к распространению царства Христова. Он восхотел, под конец дней своих, возвестить еще слово крестное и просвещенным эллинам, как возвещал доселе варварам в пустынях Скифии, и для сего отплыл в Ахаию, которая должна была сделаться последним поприщем апостольских трудов его. Свет небесный, внезапно озаривший лицо апостола при самом вступлении его в пределы Ахаии, был предвестником и залогом того невечернего света, к которому в скором времени он имел быть воззван.
Посетив многие города Греции, св. Андрей прибыл в Патры Ахайские (нынешний Патрас). Тогда уже свирепствовало первое гонение на христиан, воздвигнутое Нероном; несмотря на то, высокая проповедь апостола и чудодейственная сила его над болящими и бесноватыми, в краткое время привлекли многих ко Христу; храмы языческие заметно пустели, а число христиан непрестанно умножалось. Раздраженный этим, правитель области, Эгей, заключил св. Андрея в темницу; но любовь верных не оставила апостола и в заключении: множество народа ежедневно стекалось к темнице внимать вдохновенной проповеди Андрея, так что правитель, опасаясь народного волнения, поспешил осудить апостола на крестную смерть. Когда св. Андрей приведен был туда, где приготовлен крест, то, увидев его издали, громко воззвал: "Радуйся, кресте, плотию Христовою освященный! Прежде нежели взошел на тебя Господь мой, ты страшен был для земнородных; но теперь, когда ты вместил в себя любовь небесную, быть распростертым на тебе есть дар. Знают верные, сколько сокрыто в тебе щедрот, сколько уготовано за тебя наград. Безбоязненно и весело иду я к тебе; но и ты с веселием и радостию приими меня, ученика распявшегося на тебе Господа". Два дня продолжались крестные страдания св. Андрея; во все это время он не переставал поучать толпы народа, окружавшие крест его; под конец второго дня небесный свет озарил лицо его; и страдалец мирно отошел ко Господу в 30-й день ноября, при восхождении солнца около 70-го года по Р. Х.