De traditie vertelt dat hij na het Pinksterfeest een lange reis ondernam langs de oevers van de Zwarte Zee om het Evangelie te verkondigen. Zijn reizen brachten hem naar Bityni (aan de kust van Turkije), naar Efeze, Mesopotami, de huidige Oekraïne, Tracië (de streek tussen de Bosporus en de Donau), Byzantium en ten slotte naar Achaja, gelegen in het noorden van de Peloponnesus. Hier werd hij, in Patras, onder keizer Nero in het jaar 60 gekruisigd. Het kruis waarop hij werd terechtgesteld, had de vorm van een X en zo’n kruis wordt sindsdien het Andreaskruis genoemd.
In de 4e eeuw werden zijn relieken overgebracht naar Constantinopel. Nu liggen ze in Amalfi in Italië. In de jaren zestig werd een groot gedeelte van de relieken van de heilige en van zijn kruis aan de Griekse kerk teruggeven. In de stad Patras werd een kerk gebouwd om de relieken te bewaren.
Het voorwerp waarmee de heilige Andreas wordt afgebeeld is een kruis met twee gelijke balken, het zogenaamde Andreaskruis. Soms wordt de voormalige visser ook afgebeeld met een visnet waaruit twee viskoppen tevoorschijn komen.