Σύμφωνα με την παράδοση, οι δύο Αθηναίοι μοναχοί Σωφρόνιος και Βαρνάβας, κατά κόσμον Σωτήριχος και Βασίλειος (ανιψιός και θείος) ίδρυσαν τη Σταυροπηγιακή Ιερά Μονή Σουμελά περί τα τέλη του 4ου αιώνα, νότια της Τραπεζούντας, κοντά στα χωριά Σκαλίτα και Λαραχανή του όρους Μελά.
Πάντα σύμφωνα με την παράδοση, η εικόνα μυστηριωδώς το 380 μ.Χ., την εποχή που βασίλευε ο Μέγας Θεοδόσιος, έφυγε «πετώντας» προς Ανατολάς από το χώρο όπου φυλασσόταν στην Αθήνα, και μετεγκαταστάθηκε στα βορειοανατολικά του Πόντου.
Στη συνέχεια, και στο διάστημα που την αναζητούσαν οι πιστοί, εμφανίστηκε «κατ’ όναρ» σε έναν ευλαβή ιερέα, τον τριαντάχρονο τότε Βασίλειο από την Αθήνα, γιο δυο πιστών και ευσεβών ανθρώπων, του Κωνσταντίνου και την Άννας, και στον ανιψιό του, μαζί με τον οποίο διέμενε, τον δεκαοκτάχρονο ιεροδιάκονο Σωτήριχο. Κατά την παράδοση, ο Βασίλειος είδε μια πανέμορφη και υπέρλαμπρη νέα στα δεξιά της Αγίας Τράπεζας, που γύρω την υπήρχαν «άπειρα» πλήθη λευκοφορεμένων νέων, απευθυνόμενη στον Βασίλειο να του λέει:
«Βασίλειε σήκω γρήγορα, μαζί με τον ανιψιό σου τον Σωτήριχο και αφού εγκαταλείψετε τα υπάρχοντα σας, να γίνετε Μοναχοί. Και συ μεν να μετονομασθείς Βαρνάβας, ο δε ανιψιός σου, Σωφρόνιος» και αφού εξήγησε ότι ήταν η Θεοτόκος Μαρία, του υποσχέθηκε ότι θα είναι κοντά τους σε όλη τη ζωή τους.
Την επομένη, που οι δυο άνδρες –φοβισμένοι σχεδόν– επισκέφθηκαν στην Αθήνα το χώρο όπου ήταν η ιερή εικόνα της Παναγίας για να προσκυνήσουν και να προσευχηθούν, άκουσαν έκθαμβοι φωνή που τους καλούσε να ακολουθήσουν την πορεία της προς τον Πόντο, η οποία τους πληροφορούσε και παράλληλα τους πρόσταζε:
«Εγώ προπορεύομαι, τέκνα, όπως προείπον, εις όπερ πάντοτε εξελεξάμην όρος του Μελά, μεθ’ υμών ούσα». Οι δύο χριστιανοί αμέσως μετά τα όσα άκουσαν από την Παναγία εκστατικοί παρακολούθησαν την ουράνια πτήση της, βλέποντας την Αγία Εικόνα να την κρατούν δύο Άγγελοι και να την βγάζουν από το χώρο της Εκκλησίας και στη συνέχεια να ανεβαίνει προς τους ουρανούς «μετεωροπορώντας προς Ανατολάς» και να χάνεται μέσα στα σύννεφα.
Τις επόμενες μέρες οι δύο πιστοί χριστιανοί επισκέφθηκαν τον ηγούμενο Θεόδουλο που εξ αποκαλύψεως γνώριζε για το τι τους είχε συμβεί, και αφού πρώτα τους κατήχησε στον μοναχικό βίο, στην συνέχεια τους έχρισε μοναχούς δίνοντας τους τα ονόματα Βαρνάβας και Σωφρόνιος.
Την επόμενη νύχτα, την ώρα της προσευχής, οι δύο νέοι μοναχοί αντίκρισαν μέσα σε ένα υπέρλαμπρο φως τη Θεοτόκο να τους προσφωνεί με τα νέα τους ονόματα λέγοντας: «Βαρνάβα και Σωφρόνιε, ειρήνη σε εσάς, γιατί εγώ είμαι, μην φοβάστε, αλλά συνεχίστε το δρόμο σας με την εν Κυρίω χάριν, έως ότου φθάσετε στο όρος στο οποίο σας οδηγώ».
Με μοναδικά τους εφόδια την πίστη τους στο Θεό και την αγάπη τους στην Θεοτόκο, οι δύο μοναχοί, ακολουθώντας ένα υπέρλαμπρο φως, ταξίδεψαν επί τρία χρόνια, αντιμετωπίζοντας δυσκολίες, δοκιμασίες και επιθέσεις. Ήρθαν σε επαφή με άλλους μοναχούς και απλούς χριστιανούς στην Αθήνα, στην Κόρινθο, τα Μετέωρα, τη Λάρισα, τη Θεσσαλονίκη. Προσκύνησαν τον Άγιο Δημήτριο, επισκέφθηκαν τη Χαλκιδική, το Άγιον Όρος, όπου παρέμειναν για λίγους μήνες, μέχρι για τη Μαρώνεια της Θράκης. Από τη Μαρώνεια πεζοπορώντας μέσω Ραιδεστού έφτασαν στην Έφεσο, στη Σμύρνη, πέρασαν απέναντι στη Μυτιλήνη και από εκεί, αφού επιβιβάστηκαν σε πλοίο, έφτασαν στην Κωνσταντινούπολη.
Αφού παρέμειναν για λίγο εκεί, αναχώρησαν για τον Πόντο, και ύστερα από πεζοπορία δεκατριών ημερών έφτασαν στην Τραπεζούντα.
Εκεί, αφού φιλοξενήθηκαν από Έλληνες που από αιώνες ζούσαν στα παράλια του Εύξεινου Πόντου, προσκύνησαν τη Θεοτόκο τη Χρυσοκέφαλο και την κάρα του προστάτη της Τραπεζούντας Αγίου Ευγένιου, και στη συνέχεια περπάτησαν προς το εσωτερικό του Πόντου. Μόλις πέρασαν «τας Καρυάς», δηλαδή το σημερινό «Τζεβισλούκ» της Τουρκίας, και έφτασαν στο σημείο όπου συγκλίνουν τρεις οροσειρές και ενώνουν τα νερά τους τα δυο ποτάμια, ο Πυξίτης και της Λαραχανής, σύμφωνα πάντοτε με την παράδοση, τους φιλοξένησε ένας χωρικός και τους φίλεψε φρέσκα ψάρια. Τους εξήγησε μάλιστα ότι τα είχε ψαρέψει το πρωί από τον ποταμό Πυξίτη, που οι πηγές του ξεκινούν το ταξίδι τους από το όρος Μελά. Ακούγοντας οι μοναχοί το όνομα του βουνού, άφησαν το φαγητό τους στη μέση και παρακάλεσαν τον χωρικό να τους δείξει το δρόμο για το όρος Μελά. Ο φιλόξενος χωρικός τούς εξήγησε ότι θα έπρεπε να ακολουθήσουν τη ροή του Πυξίτη, για να φτάσουν στο όρος Μελά. Έτσι, την επομένη το πρωί κατευθύνθηκαν στους πρόποδες του ολοκάθετου και επιβλητικού όρους Μελά.
Στην πολύωρη αυτή πρωινή πεζοπορία τους εντυπωσιάστηκαν από την άγρια φύση που αντίκρισαν, τα μεγάλα σε όγκο άσκεπα βουνά με τις επίπεδες και τις κωνικές κορυφές, το δάσος που μέχρι τότε ήταν απάτητο, παρθένο, αφιλόξενο, χωρίς ένα μονοπάτι για να μπορούν να διαβούν.
Έτσι αναγκάστηκαν να σκαρφαλώσουν σε βράχους και να στηρίζονται σε κορμούς δένδρων για να το ανέβουν. Ύστερα από πολύωρη και εξαντλητική προσπάθεια κατάφεραν να σκαρφαλώσουν στην κορυφή του βουνού. Έξαφνα αντίκρισαν μπροστά τους μια σπηλιά. Η παράδοση αναφέρει ότι παρόλο που βρήκαν την σπηλιά η πρόσβασή τους εκεί ήταν αδύνατη, αφού δυσκολεύονταν να αναρριχηθούν από το σημείο που ήταν, αλλά και οι δυνάμεις τους τους είχαν ήδη εγκαταλείψει. Ανήμποροι να κάνουν κάτι οι ίδιοι για να φθάσουν στην είσοδο της σπηλιάς, προσευχήθηκαν και πάλι στην Θεομήτορα, παρακαλώντας να τους δώσει δύναμη και να τους βοηθήσει να ξεπεράσουν και αυτό το πρόβλημα.
Τότε ένα μεγάλο έλατο, που βρισκόταν ανάμεσα στην σπηλιά και το σημείο όπου κρεμόντουσαν σχεδόν οι ίδιοι, σαν από θαύμα, έγειρε απαλά προς το μέρος τους, σαν γέφυρα, ενώνοντας την κορυφή μαζί τους.
Πλησιάζοντας στην κορυφή του βουνού, στα 1.063 μέτρα, ανακάλυψαν την είσοδο της μεγάλης κόγχης. Την ώρα που προσπαθούσαν να περάσουν μέσα της, εκατοντάδες χελιδόνια, ξαφνιασμένα από την απροσδόκητη ανθρώπινη επίσκεψη, πέταξαν πάνω από το κεφάλι τους και τους χτύπησαν αφήνοντας τη θαλπωρή της σπηλιάς για πάντα. Την ίδια ώρα οι μοναχοί δέχτηκαν μια χρυσαφένια λάμψη στο πρόσωπο τους, η οποία πλημμύρισε συγχρόνως και όλο τον γύρω χώρο. Μπαίνοντας σκυφτά στο βάθος της σπηλιάς αντίκρισαν πάνω σε έναν βράχο, εκστατικοί, το εικόνισμα της Παναγίας!
Εκεί, στην κόγχη του βουνού, με τροφή τα άγρια χόρτα που φύτρωναν στην περιοχή, οι δύο μοναχοί για 17 μέρες και νύχτες καθάριζαν το μέρος, για να το κάνουν προσβάσιμο και κατοικήσιμο, ξεπερνώντας πολλές δυσκολίες και εμπόδια.
Η παράδοση και πάλι αναφέρει ότι στο διάστημα που οι μοναχοί αγωνίζονταν να βρουν τρόπους να χτίσουν τη Μονή, η Θεία Πρόνοια ονειρεύει τον ηγούμενο της Μονής Ιωάννου Προδρόμου του Βαζελώνα (κοντά στα χωριά Σαχνόη και Θέρσα) και τον προστάζει: «ουκ είπον σοι ανάστα και της εν τω όρει φωνής. Επήκοος πρόσδραμε, ίνα μη ολιγορήσης των εμών λόγων».
Ο ηγούμενος τότε έδωσε εντολή στους μοναχούς Βαρνάβα, Ιουστίνο και Νικήτα να φορτώσουν δυο γαϊδουράκια με τρόφιμα και να κινηθούν προς αναζήτηση των δυο μοναχών. Οδοιπορούντες οι μοναχοί, μέσα από δύσκολες συνθήκες κατάφεραν να φτάσουν στην σπηλιά όπου είχε εγκατασταθεί η εικόνα της Παναγίας. Προσκύνησαν τη χάρη της, παρέδωσαν τα τρόφιμα στους μοναχούς και επέστρεψαν στη Μονή Βαζελώνα όπου ενημέρωσαν τον ηγούμενό τους. Ο ηγούμενος, θεωρώντας δώρο Θεού την παρουσία της Παναγίας στην περιοχή του Πόντου, έδωσε διαταγή και μια μεγάλη κουστωδία μοναχών, με φορτωμένα τα απαραίτητα υποζύγια, πήγε κοντά στους Βαρνάβα και Σωφρόνιο και εργάστηκε μαζί τους για την ανιστόρηση της πρώτης Μονής, του Αρχάγγελου Μιχαήλ.
Αργότερα οι μοναχοί της Σουμελά, ως δείγμα σεβασμού και αγάπης στην κτήτορα μονή, κάθε χρόνο μέχρι το 1800, σύμφωνα με τον ηγούμενο της Μονής Βεζελώνα Πανάρετο Τοπαλίδη, έστελναν στον Βαζελώνα πενήντα άσπρα (χρήματα της εποχής), δώδεκα κιλά κερί, λάδι, και κάθε επτά χρόνια ένα γαϊδουράκι που έφερε κρεμασμένο στο λαιμό του ένα γράμμα με τις ευχαριστίες των μοναχών.
Προηγουμένως, και ύστερα από τις πολυήμερες προσευχές τους, στην αγωνία τους οι δύο μοναχοί για την αναζήτηση νερού, στο σημείο όπου είχαν βρει θρονιασμένο το εικόνισμα της Παναγίας άρχισε να αναβλύζει νερό μέσα από τις άνυδρες πέτρες. Ενώ –όπως λέει η παράδοση– από την Εικόνα ακούγεται και πάλι η φωνή της Θεοτόκου: «Ιδού, σας δίνεται νερό από ξερή πέτρα, που δεν θα είναι μόνο για τις ανάγκες σας, αλλά θα θεραπεύει και κάθε πάθος αυτών που θα προσέρχονται με πίστη».
Από τότε και για 16 αιώνες οι αγιασμένες αυτές πέντε σταγόνες καθαρού νερού δεν σταμάτησαν να στάζουν, καθημερινά, μέσα σε μια φυσική λεκάνη που είχε σχηματιστεί από ύψος περίπου 60 μέτρων. Αυτές οι θεραπευτικές ιδιότητες του αγιάσματος έκαναν πασίγνωστο το μοναστήρι, όχι μόνο τους χριστιανούς της περιοχής, αλλά και τους μουσουλμάνους, που συνεχίζουν μέχρι και σήμερα να προστρέχουν σε αυτό και να ζητούν τη χάρη της Παναγίας.
Στο διάστημα αυτό, στα γύρω από το όρος Μελά χωριά μαθεύτηκε η εγκατάσταση των δύο μοναχών στα υψώματά του και αυθόρμητα οι κάτοικοι τους προσέτρεξαν σε βοήθεια εκείνων.
Συγκεκριμένα οι κάτοικοι του παρακείμενου χωριού Κουσπίδι, βλέποντας τη θεοσέβεια των δύο μοναχών, αλλά και τις δυσκολίες που αντιμετώπιζαν, τους τροφοδοτούσαν με τρόφιμα και οικοδομικά υλικά.
Έτσι, με τη βοήθεια και των μοναχών της Μονής Βαζελώνα, το πρώτο κελί έχτισαν οι δύο μοναχοί αριστερά από το κλιμακοστάσιο που βρίσκεται στο εσωτερικό της Μονής. Ο πρώτος ναός που έχτισαν ήταν αυτός του Αρχάγγελου Μιχαήλ, που ανακαινίστηκε κατά καιρούς και μάλιστα σωζόταν μέχρι τις αρχές του 20ού αιώνα (1930).
Στα θυρανοίξια και τον καθαγιασμό του ναού του Αρχαγγέλου Μιχαήλ, ο επίσκοπος Τραπεζούντας έστειλε μόνο ιερείς. Όταν όμως ολοκληρώθηκε ο ναός της Παναγίας το 286 μ.Χ., επί αυτοκρατορίας Θεοδοσίου του Μεγάλου, ο καθαγιασμός του και τα εγκαίνια στο όνομα της Θεοτόκου έγιναν παρουσία του επισκόπου Τραπεζούντος και του Ρωμαίου διοικητή Αυγουστάλιου Κορτίκιου –που στην συνέχεια ασπάστηκε τον Χριστιανισμό–, επισήμων, και πλήθους πιστών από τα γύρω χωριά.
Όπως γράφει ο Επαμεινώνδας Κυριακίδης, πριν από την αναχώρησή του ο Κορτίκιος, στην πρώτη επίσκεψή του, προσέφερε στους δύο μοναχούς ποσότητα χρυσού. Οι μοναχοί, αφού τον ευχαρίστησαν, του επέστρεψαν την ευγενική προσφορά του με την παρατήρηση ότι «όσοι διαχειρίζονται και υπηρετούν το πολύτιμο αυτό κόσμημα, την εικόνα της Θεοτόκου, δεν χρειάζονται όλα όσα είναι απαραίτητα γι’ αυτούς που διαχειρίζονται φθαρτές αξίες». Και θα τους είναι αρκετό μόνο να παραβρεθεί ο ίδιος με τον οικείο επίσκοπο στα εγκαίνια της Μονής. Γι’ αυτό και ο Αυγουστάλιος Κορτίκιος μπορεί να θεωρηθεί ο κτήτορας της πρώτης Μονής.
Παρ’ όλα αυτά ο Κορτίκιος, αφού πήρε πίσω τις χρυσές λίρες που έδωσε, πριν την αναχώρηση του, άφησε σε κάποιο κρυφό σημείο της Μονής ένα πουγκί γεμάτο με ασημένια νομίσματα.
Με αυτήν τη δωρεά οι μοναχοί αργότερα άνοιξαν δρόμο προς τη Μονή, για να είναι προσβάσιμη σε όσους επιθυμούσαν να την επισκεφθούν, άλλα έχτισαν και κοιμητήρια κάτω από το βήμα της Μονής.
Στη συνέχεια, και αφού η εικόνα της Παναγίας απέκτησε εξαιρετική φήμη και άρχισαν να συρρέουν πιστή για χάρη της, προσήλθαν πολλοί μοναχοί και συγκρότησαν το κοινόβιο του μοναστηριού. Μάλιστα οι μοναχοί, θέλοντας να παράσχουν χώρο φιλοξενίας στους προσκυνητές, έχτισαν στην πεδιάδα κάτω από την Μονή έναν ξενώνα.
Παράλληλα οι μοναχοί Βαρνάβας και Σωφρόνιος επέκτειναν τη δράση τους και πέρα από τη Μονή. Ο Βαρνάβας έχτισε το ναό του Αγίου Κωνσταντίνου και Ελένης στο χωριό Σκαλίτα, που βρισκόταν σε απόσταση περίπου τριών ωρών απέναντι από τη Μονή, ενώ ο Σωφρόνιος το εκκλησάκι της Αγίας Βαρβάρας, εκατοντάδες μέτρα λίγο κάτω από τη Μονή Σουμελά και παράλληλα με αυτήν. Ήταν ο χώρος που 1.500 χρόνια μετά έγινε το ασφαλές κρησφύγετο για την Ιερή Εικόνα και τα άλλα δύο κειμήλια της Μονής, το Ευαγγέλιο του Οσίου Χριστοφόρου και το σταυρό του αυτοκράτορα Μανουήλ Γ’, που περιείχε κομμάτι τιμίου ξύλου.
