Το 30 π. Χ., μετά την καταστροφή της ελληνιστικής Πέλλας, ο Οκταβιανός ίδρυσε σε απόσταση 1,5 χλμ. δυτικά της ελληνιστικής πρωτεύουσας, στην περιοχή βόρεια των”Λουτρών του Μεγάλου Αλεξάνδρου”, σε νέα επίκαιρη θέση επί της Εγνατίας οδού, τη ρωμαϊκή αποικία της Πέλλας, γνωστή και ως Colonia Pella. Οικοδομικά κατάλοιπα, νομίσματα, και αντιπροσωπευτική κεραμική σηματοδοτούν την αναβίωση της πόλης κατά την παλαιοχριστιανική περίοδο. Στη φάση αυτή, ο οχυρωματικός περίβολος της πόλης. αισθητά μικρότερος, περικλείει τμήμα της άλλοτε ρωμαϊκής αποικίας. Ανασκαφικές έρευνες που πραγματοποιήθηκαν στο βορειοδυτικό τμήμα της πόλης μαρτυρούν ότι ο χρόνος κατασκευής των τειχών της πόλης μπορεί να συνδεθεί με το τέλος του 3ου αιώνα, ενώ τα κινητά ευρήματα βεβαιώνουν ότι ο χρόνος λειτουργίας της οχύρωσης ήταν ολόκληρος ο 4ος και 5ος αιώνας. Πιθανή ωστόσο ταύτιση της πόλης με τα “Βασιλικά Αμύντου” που μνημονεύονται από τον ιστορικό Προκόπιο ως ένα από τα φρούρια της περιοχής που επισκευάστηκαν από τον Ιουστινιανό, μαρτυρεί ανακαίνιση και λειτουργία του τείχους και κατά τον 6ο αιώνα.Την οικοδομική δραστηριότητα που αναπτύχθηκε στην πόλη κατά πρώιμη βυαντινή περίοδο πιστοποιεί μεγαλοπρεπής ναός που εντοπίστηκε βόρεια των “Λουτρών του Μεγάλου Αλεξάνδρου”. Τοίχοι κτιρίων που τον πλαισιώνουν βόρεια και νότια μαρτυρούν ότι η εκκλησία δεν ήταν ένα μεμονωμένο λατρευτικό κτίσμα αλλά εντασσόταν σε ένα ευρύτερο μνημειακό συγκρότημα. Ταυτόχρονα η παρουσία τείχους σε μικρή απόσταση ανατολικά καθιστά ελκυστική την ταύτισή του με οχυρωματικό περίβολο, ο οποίος περιέκλειε το συγκρότημα. Τα ανασκαφικά στοιχεία μαρτυρούν ότι η βασιλική ιδρύθηκε στο β’ μισό του 5ου αιώνα και καταστράφηκε στις αρχές του 7ου αι., ο χώρος όμως συνέχισε να βρίσκεται σε χρήση μερικούς ακόμη αιώνες, λειτουργώντας ως οικιστική εγκατάσταση. Τέλος, από τα οψιμότερα οικοδομικά λείψανα στο χώρο είναι ο μονόχωρος ναϊσκος της ύστερης βυζαντινής περίοδου ο οποίος οικοδομήθηκε σε μικρή απόσταη δυτικά της βασιλικής.
Στον αρχαιολογικό χώρο της Ρωμαϊκής Αποικίας της Πέλλας, σε μικρή απόσταση βόρεια των λεγόμενων “Λουτρών του Μεγάλου Αλεξάνδρου” ανασκάφηκε μεγαλοπρεπής ναός στον τύπο της τρίκλιτης ξυλόστεγης βασιλικής με νάρθηκα, εξωνάρθηκα και αίθριο. Ο ναός είναι συνολικών διαστάσεων 42,50 Χ 20,20μ. Δύο χτιστοί στυλοβάτες, σε απόσταση 4 μ. από το βόρειο και νότιο τοίχο αντίστοιχα, στήριζαν κιονοστοιχίες διαιρώντας το εσωτερικό του ναού σε τρία κλίτη. Ανατολικά προεξέχει η κεντρική αψίδα του Ιερού Βήματος, η οποία είναι ημικυκλική, χορδής 7,50 μ., στο εσωτερικό της οποίας διαμορφώνεται χτιστό, ημικυκλικό, βαθμιδωτό σύνθρονο, επενδεδυμένο με μαρμάρινες πλάκες. Σε επαφή με τη δυτική απόληξη του συνθρόνου διαμορφώνονται τα συμψέλλια, τα οποία είναι καλυμμένα με πλάκες μαρμάρου. Η ανασκαφή στο χώρο αποκάλυψε και τμήμα του φράγματος του πρεσβυτερίου, το οποίο είναι πιόσχημο και φέρει προστώο στο μέσον της δυτικής του πλευράς.
Ιδαίτερα εντυπωσιακά μαρμαροθετήματα με πολύχρωμα πλακίδια καλύπτουν τα δάπεδα του Ιερού Βήματος, του κεντρικού κλίτους και του κεντρικού τμήματος του νάρθηκα της βασιλικής, ενώ χονδρό ψηφιδωτό με γεωμετρικό θεματολόγιο κοσμούν τα δάπεδα των πλαγίων κλιτών, του νάρθηκα και του εξωνάρθηκα. Η χρονολόγηση των ψηφιδωτών στο β’ μισό του 5ου αιώνα οδηγεί σε μια χρονολόγηση της κατασκευής του ναού την περίοδο αυτή. Τα ανασκαφικά δεδομένα μαρτυρούν ότι μετά από καταστροφή που υπέστη το μνημείο, πραγματοποιήθηκε στα μέσα του 6ου αιώνα ευρεία ανακαίνιση, η οποία άλλαξε την αρχιτεκτονική μορφή και εν μέρει τη διακόσμησή του. Πάνω από τα πλάγια κλίτη και το νάρθηκα κατασκευάστηκαν υπερώα, στα οποία οδηγούσε κτιστή κλίμακα που εντοπίστηκε στο νάρθηκα. Στο βόρειο κλίτος προστέθηκε και δεύτερος στυλοβάτης, σε μικρή απόσταση από τον κύριο, ο οποίος έφερε κιονίσκους σε όλο του το μήκος και ανέκοπτε την πρόσβαση των πιστών στο κεντρικό κλίτος. Η έρευνα στα νότια της βασιλικής αποκάλυψε μνημειακή κλίμακα, η οποία συνέδεε πιθανότατα τη βασιλική με κάποια οδική αρτηρία της πόλης. Αποτελείται από τέσσερις βαθμίδες μέσω των οποίων οι προσκυνητές ανέρχονταν σε έναν διάδρομο-στοά. Ο διάδρομος αυτός βόρεια επικοινωνούσε μέσω θυρών με το νάρθηκα και τον εξωνάρθηκα, ενώ ανατολικά κατέληγε σε ένα αυτοτελές πρόσκτισμα, το οποίο θα μπορούσε να συνδεθεί με βαπτιστήριο. Δεν είναι γνωστή η αιτία και ο χρόνος καταστροφης του συγκροτήματος. Ωστόσο, τα ανασκαφικά στοιχεία μαρτυρούν ότι η καταστροφή προκλήθηκε από κάποιο αιφνίδιο γεγονός (πιθανότατα σεισμό), ο οποίος θα πρέπει να τοποθετηθεί γύρω στις αρχές του 7ου αιώνα, περίοδο κατά την οποία εγκαθίστανται στην περιοχή σλαβικά φύλα. Μετά την καταστροφή του ναού, ο χώρος εξακολούθησε να χρησιμοποιείται, όχι όμως με τη λατρευτική του χρήση, αλλά ως χώρος οικιστικής εγκατάστασης.
Τη μεγάλη σημασία του συγκροτήματος μαρτυρεί η παρουσία τείχους σε μικρή απόσταση ανατολικά της βασιλικής, ο οποίος θα μπορούσε να λειτουργεί ως περίβολος που περιέκλειε το συγκρότημα παρέχοντας προστασία και ασφάλεια στο εσωτερικό του.