The arrival of the Apostie Paul in Macedonia and the founding of Europe's first Christian communities at Philippi, Thessaloniki, and Beroea, were a landmark in the history of Western civilisation. Archaeological finds from the fourth century A.D., which was when Constantine the Great (306-37) decided to found Constantinople (330), separate the Eastern Roman Empire from Rome, and wed the two worlds of paganism and Christianity, show the strongly Hellenic flavour of Christianity in Macedonia.

At Philippi, for instance, a pagan heroon functioned side by side with the city's first Christian church, dedicated to St Paul; and in Thessaloniki a local martyr, St Demetrius, replaced the city's age-old deity Cabirus in the hearts and minds of the Thessalonians. Until Justinian I's time (527-65), Christianity in Macedonia was closely interwoven with the Greek and Roman tradition. Tombs found in Thessaloniki are decorated with wall-paintings which accompanied the deceased on their final journey with, symbolic representations of the promised Paradise; the angels with their wreaths and colourful banners are frequently reminiscent of the cupids of antiquity. Large and small church complexes were built in the Macedonian cities and countryside and adorned with lovely mosaic floors with images of deer (Amphipolis), doves (Akrini, near Kozani), and symbolic representations of Paradise (Heraclea Lyncestis). A few wall mosaics from this period survive in churches in Thessaloniki (in the Rotunda of St George, St Demetrius, Latomou Monastery, and Acheiropoietos) .

Σταθμός στην ιστορία του Δυτικού πολιτισμού υπήρξε το κήρυγμα του Παύλου στη Μακεδονία και η ίδρυση των πρώτων στην Ευρώπη χριστιανικών κοινοτήτων στους Φιλίππους, τη Θεσσαλονίκη και τη Βέροια. Αρχαιολογικά ευρήματα του 4ου αι. μ.Χ., της εποχής που ο Μ. Κωνσταντίνος (306-337) αποφάσισε ιδρύοντας την Κωνσταντινούπολη (330) να αποδεσμεύσει το Ανατολικό Ρωμαϊκό Κράτος και να παντρέψει τους δύο κόσμους, τον εθνικό και το χριστιανικό, δείχνουν πόσο ελληνικός ήταν ο χριστιανισμός στη Μακεδονία.

Στους Φιλίππους εθνικό ηρώο συλλειτουργούσε δίπλα- δίπλα με τον πρώτο δημόσιο χριστιανικό ευκτήριο οίκο της πόλης αφιερωμένο στον απόστολο Παύλο και στη Θεσσαλονίκη ένας ντόπιος μάρτυρας, ο άγιος Δημήτριος, αντικατέστησε τον πατρώον Θεό Κάβειρο στις ψυχές των Θεσσαλονικέων. Στους αιώνες έως τον Ιουστινιανό Α' (527-565) ο χριστιανισμός στη Μακεδονία συμπλέκεται με την ελληνική και ρωμαϊκή παράδοση. Τάφοι στη Θεσσαλονίκη φέρουν τοιχογραφίες που συντροφεύουν το νεκρό στο τελευταίο του ταξίδι με παραστάσεις που συμβολίζουν τον υποσχεθέντα Παράδεισο, όπου συχνά οι απεικονιζόμενοι άγγελοι κρατώντας στεφάνια και πολύχρωμες ταινίες συγχέονται με τους ερωτιδείς της Αρχαιότητας. Μεγάλα και μικρότερα εκκλησιαστικά συγκροτήματα κτίζονται στις πόλεις και στην ύπαιθρο της Μακεδονίας. Κοσμούνται με ωραιότατα ψηφιδωτά δάπεδα με παραστάσεις ελαφιών (Αμφίπολης), περιστεριών (Ακρινή Κοζάνης) και συμβολικές παραστάσεις Παραδείσου (Ηράκλεια Λυγκηστίδα). Λίγα εντοίχια ψηφιδωτά της περιόδου αυτής σώζονται σε ναούς της Θεσσαλονίκης (Ροτόντα Αγίου Γεωργίου, Άγιος Δημήτριος, μονή Λατόμου, Αχειροποίητος).