Από τους πρώτους αιώνες το φως τής χριστιανικής πίστεως έφθασε και στον ανατολικό μυχό τού Ευξείνου Πόντου. Ο εκχριστιανισμός όμως τών διαφόρων φύλων τής Κολχίδος, τής περιοχής ανάμεσα στον Καύκασο και την Κασπία, συντελέσθηκε βαθμιαίως.

Τα κυριότερα από αυτά τα φύλα ήταν κατά μήκος τής παραλίας: Νοτίως μεν τού ποταμού Φάσιδος οι Μαλεχόνες, οι Ζυδρείτες, οι Λαζοί (οι οποίοι ήσαν οι σημαντικότεροι και από αυτούς όλοι οι Κόλχοι ονομάσθηκαν αργότερα Λαζοί), βορείως δε τού ποταμού Φάσιδος οι Αψίλιοι, οι Αβασγοί και οι Σανίγες, γύρω από τη Διοσκουριάδα ή Σεβαστούπολη, οι Κοραξοί, γύρω από τον ποταμό Κόρακα, και στα βορειοδυτικά τής Κολχίδος οι Ηνίοχοι και οι Σοάνες. Οι περισσότεροι από αυτούς ήταν συνήθως υπήκοοι τών Λαζών (Χρυσάνθου, Μητρ. Τραπεζούντας, "Η Εκκλησία τής Τραπεζούντος", Αθήναι 1933, σ. 40).

Στο εσωτερικό τής χώρας κατοικούσαν οι Μέσχοι ή Μαύραλοι, ενώ ανατολικότερα οι Ίβηρες. Η παράδοση αναφέρει ότι ο απόστολος Ανδρέας, όταν κήρυττε το Ευαγγέλιο στη Θράκη, το Βυζάντιο, τη Βιθυνία, τον Πόντο, τη Λαζική  και Σκυθία, επισκέφθηκε τις σημαντικότερες παραλιακές πόλεις τής Κολχίδος και τού Πόντου (Νικήτα Παφλαγόνος, "Λόγος εις τον Άγιον Ανδρέαν", PG 105, 64-68). Κύριοι όμως φορείς τής Χριστιανικής πίστεως στις περιοχές αυτές ήσαν οι Χριστιανοί έμποροι, οι αιχμάλωτοι και, κυρίως οι φλογεροί μοναχοί τού 4ου αιώνα.

Η εύκολη επαφή με διάφορες παραλιακές Χριστιανικές πόλεις τού Πόντου βοήθησε στη βαθμιαία εξάπλωση τού Χριστιανισμού μεταξύ τών Λαζών. Ο πλήρης όμως εκχριστιανισμός τους συντελέσθηκε τον 6ο αιώνα, επί Ιουστίνου τού Α΄ (522), όταν ο βασιλιάς τών Λαζών Τζάθος "ήλθε προς Ιουστίνον εις το Βυζάντιον και παρεκάλεσε τον βασιλέα γενέσθαι αυτόν Χριστιανόν και υπ' αυτού αναγορευθήναι βασιλέα τών Λαζών" (Θεοφάνους Χρονογραφία, Α΄., έκδ. Βόννης, σ. 259).

Όταν επέστρεψε στη Λαζική τον μιμήθηκαν όλοι οι υπήκοοί του. Ο εκχριστιανισμός τών Λαζών είχε ως άμεσο αντίκτυπο τη διάδοση τής Χριστιανικής πίστεως και στους υποτελείς σε αυτούς τους λαούς. Την εποχή τού Ιουστινιανού, η Εκκλησία τών Λαζών ήταν κανονικώς οργανωμένη, έχοντας επισκόπους, οι οποίοι μάλιστα έστελναν ιερείς στα φύλα που υπάγονταν σ' αυτούς (Προκοπίου, "Γοτθικοί πόλεμοι", IV, 2, έκδ. Βόννης, σ. 466). Γι' αυτό ο αυτοκράτορας περιορίσθηκε στο να ανακαινίσει την Εκκλησία, "αρχαίαν τε ούσαν και σαθράν τη οικοδομία γεγενημένην" (Προκοπίου "Περί κτισμάτων", ΙΙΙ, 7, 6-8).

Στον κατάλογο τών Μητροπόλεων τού Ψευδοεπιφανίου (650) αναφέρεται η επαρχία "Λαζικής" με μητροπολίτη τον Φάσιδος και 4 επισκοπές: Ροδοπόλεως, Σασινών, Πετρών ή Πέτρας και Ζιγανέων. Ο Πέτρας Θεόδωρος και ο Φάσιδος Ιωάννης έλαβαν μέρος στην ΣΤ΄ Οικουμενική Σύνοδο (680-681).