Πρώτος κήρυκας του ευαγγελίου στην περιοχή του Πόντου ευρύτερα, και στην Τραπεζούντα ειδικότερα, θεωρείται ο απόστολος Ανδρέας. Με τη διάδοση του χριστιανισμού δημιουργήθηκαν και οι πρώτες επισκοπές. Τον 4ο αιώνα η Επισκοπή Τραπεζούντος μαρτυρείται στα πρακτικά της Α΄ Οικουμενικής Συνόδου (325), καθώς και στις τοπικές Συνόδους της Άγκυρας, της Νεοκαισάρειας και των Γαγγρών.
Πιθανόν αμέσως μετά τη δημιουργία του θέματος Χαλδίας η Τραπεζούντα αναδείχθηκε σε μητρόπολη, αφού αποσπάστηκε από τη μητρόπολη του Πολεμωνιακού Πόντου στην οποία υπαγόταν ως επισκοπή. Ο πρώτος ιεράρχης Τραπεζούντας που φέρει τον τίτλο του μητροπολίτη είναι ο Χριστόφορος (γύρω στο 787). Στην εποχή του Λέοντος ΣΤ΄ του Σοφού η Τραπεζούντα κατείχε την 33η θέση στην ιεραρχία των μητροπόλεων, με επτά και αργότερα με δεκαπέντε υποκείμενες επισκοπές. Κατά την ταραγμένη περίοδο του 12ου αιώνα ο χριστιανικός πληθυσμός του Πόντου μειώθηκε δραματικά. Μεταξύ των λίγων μητροπόλεων που απέμειναν εν ενεργεία μόνο της Τραπεζούντας φέρεται να είχε δύο επισκοπές. Πρόβλημα αποτελεί για την έρευνα ο γεωγραφικός εντοπισμός των περισσότερων επισκοπών της Μητρόπολης Τραπεζούντος, η ταύτισή τους με οικισμούς και ο καθορισμός των ορίων τους. Επίσης, αξιοσημείωτο είναι το γεγονός ότι η πλειονότητα των ονομάτων των επισκοπών είναι βαρβαρικά.
Η Εκκλησία της Τραπεζούντας θα πρέπει να συμμετείχε στον εκχριστιανισμό ορισμένων φύλων που ζούσαν στην ενδοχώρα της. Πρόκειται για τους Τζάνους, τους Λαζούς, τους Αψιλίους, τους Μόσχους ή Μέσχους και τους Αβασγούς, ο εκχριστιανισμός των οποίων γινόταν παράλληλα με την επέκταση του βυζαντινού κράτους ανατολικότερα, κατά τον 6ο αιώνα.
Μετά την κατάκτηση της Κωνσταντινούπολης από τους Λατίνους το 1204, το εξόριστο στη Νίκαια Οικουμενικό Πατριαρχείο αντιτάχθηκε στη δραστηριότητα των Αλεξίου Α΄ και Δαβίδ, ιδρυτών της Αυτοκρατορίας των Μεγάλων Κομνηνών. Το γεγονός αυτό επέφερε κρίση στις σχέσεις του Πατριαρχείου με τη Μητρόπολη Τραπεζούντος, η οποία εκτονώθηκε μόλις το 1261 με την ανακατάληψη της Κωνσταντινούπολης και την επιστροφή του Οικουμενικού Πατριαρχείου στην έδρα του. Οι μεταξύ τους σχέσεις συσφίχθηκαν αργότερα, γύρω στο 1280, μετά την παραίτηση των Μεγάλων Κομνηνών από τον τίτλο του "βασιλέως Ρωμαίων". Παρ' όλα αυτά οι αντιθέσεις αναζωπυρώνονταν κάθε φορά που δημιουργούσαν την αφορμή επιμέρους θέματα, κοσμικά ή εκκλησιαστικά.
Οι Μεγάλοι Κομνηνοί επιχείρησαν, ήδη από την αρχή της δυναστείας τους, να ανεξαρτητοποιήσουν τη Μητρόπολη Τραπεζούντος από το Οικουμενικό Πατριαρχείο, το οποίο τελικά δέχτηκε να ψηφίζεται και να χειροτονείται ο μητροπολίτης Τραπεζούντος στην έδρα του, χωρίς να μεταβαίνει στη Νίκαια ή στην Κωνσταντινούπολη.
Στην ταραγμένη εποχή της Αυτοκρατορίας των Μεγαλοκομνηνών, ο μητροπολίτης Τραπεζούντος πολλές φορές ποίμανε άλλες χηρεύουσες μητροπόλεις. Από το 14ο αιώνα έφερε και τον τίτλο του "υπερτίμου και εξάρχου πάσης Λαζικής", ενώ "επείχε τον τόπον" (κατείχε τη θέση στην ιεραρχία του Οικουμενικού Πατριαρχείου) του μητροπολίτη Καισαρείας. Εξαιτίας της υψηλής του θέσης στην ιεραρχία και του γεγονότος ότι ήταν προκαθήμενος της Εκκλησίας της Τραπεζούντας, πρωτεύουσας της αυτοκρατορίας, ο Τραπεζούντος Δωρόθεος συμμετείχε στη Σύνοδο Φερράρας-Φλωρεντίας (1438/9). Ας σημειωθεί επίσης ότι η Τραπεζούντα είχε υπάρξει πολλές φορές το καταφύγιο των ανθενωτικών της Κωνσταντινούπολης, όπως μετά τη βίαιη επιβολή της ένωσης των Εκκλησιών από το Μιχαήλ Η΄ Παλαιολόγο (1274).
Μεταξύ των προκαθημένων της Εκκλησίας της Τραπεζούντας διακρίνονται ο όσιος Αθανάσιος ο Δαιμονοκαταλύτης (περ. 867-886) και ο Ιωσήφ Λαζαρόπουλος (1351-1364), ενώ από την ίδια πόλη έλκουν την καταγωγή τους εξέχουσες εκκλησιαστικές προσωπικότητες, όπως ο όσιος Αθανάσιος ο Αθωνίτης, ο πατριάρχης Ιωάννης Η΄ Ξιφιλίνος, ο όσιος Δωρόθεος ο Νέος και ο μητροπολίτης Νικαίας και κατόπιν καρδινάλιος Βησσαρίων.
Τέλος, αξίζει να σημειωθεί ότι κατά τη διάρκεια της Αυτοκρατορίας των Μεγάλων Κομνηνών, καθολικοί και Αρμένιοι είχαν ιδρύσει θρησκευτικά καθιδρύματα (ναούς, παρεκκλήσια, μονές) στην Τραπεζούντα, αλλά και σε άλλες πόλεις της αυτοκρατορίας, και ασκούσαν απρόσκοπτα τα θρησκευτικά τους καθήκοντα.