Ο Απόστολος των Εθνών Παύλος ήρθε στην πόλη της Βέροιας το 50–51 μ. Χ. και κήρυξε δύο φορές τη χριστιανική πίστη ακριβώς από το σημείο όπου σήμερα υψώνεται Βήμα, αφιερωμένο στην αγιότητά του. Ο χώρος αυτός κατά την πρώτη περίοδο του χριστιανισμού βρισκόταν έξω από τα τείχη της τότε πόλης και κοντά σ’ αυτήν. Σήμερα αποτελεί το σημαντικότερο σημείο αναφοράς της εκκλησιαστικής ιστορίας της Βέροιας. Το κτίσμα, που χτίστηκε προς τιμήν του Αποστόλου Παύλου, είναι πέτρινο, διακοσμημένο με τρία πολύχρωμα μεγάλα ψηφιδωτά. Κάθε Ιούνιο πραγματοποιούνται στο χώρο αυτό λατρευτικές εκδηλώσεις, που φέρουν τον τίτλο «Παύλεια» και έχουν ως αποκορύφωμα το βράδυ της 29ης του μηνός τον υπαίθριο εσπερινό, οπότε και γίνεται λιτάνευση της εικόνας του Αποστόλου.