Ἀφ’ οὗ παρῆλθον ἡμέραι τινές, λέγει πρὸς τὸν ἱερέα· «Κάτι σπουδαῖον ἔχω νὰ σοῦ εἴπω, ἀδελφέ». Ὁ δὲ ἱερεὺς τοῦ λέγει· «Εἰπέ». Λέγει τότε πρὸς αὐτόν· «Διατί λατρεύετε καὶ προσκυνεῖτε ὡς θεοὺς τὰ εἴδωλα, τὰ ὁποῖα εἶναι ξύλα καὶ λίθοι ἀναίσθητοι, ἀφοῦ ἔχοντα στόμα δὲν ὁμιλοῦν καὶ ὀφθαλμοὺς ἔχοντα δὲν βλέπουν καὶ ὦτα ἔχοντα δὲν ἀκούουν, οὔτε ὀσφραίνονται εἰς τὰς θυσίας, τὰς ὁποίας προσφέρετε εἰς αὐτά. Ἐκεῖνον δὲ τὸν ὁποῖον σέβονται καὶ πιστεύουν οἱ Χριστιανοί, αὐτὸς εἶναι Θεὸς ἀληθινός, καθὼς ἤκουσα ἀπὸ μερικοὺς Χριστιανούς, διότι καὶ θαύματα ἔκαμε πολλά, καθὼς ἀκούω καὶ πολλὰς δυνάμεις καὶ ἰατρείας». Ταῦτα ἀκούσας ὁ ἱερεὺς κατενύχθη ἀπὸ τοὺς λόγους τοῦ Αὐξιβίου καὶ δὲν ἐθυσίαζε πλέον εἰς τὰ εἴδωλα, ἀλλ’ ἀπὸ τότε καὶ εἰς τὸ ἑξῆς ἐδιδάσκετο ἀπὸ τὸν μακάριον Αὐξίβιον τὰ περὶ τῆς πίστεως τοῦ Χριστοῦ. Μὲ τοῦτον τὸν τρόπον ἔμεινεν ἱκανὸν καιρὸν εἰς τὸν τόπον ἐκεῖνον ὁ θεῖος Αὐξίβιος, μετέβαινε δὲ κρυφίως εἰς τὴν πολιτείαν ὅπου ἐδίδασκε κεκαλυμμένα καὶ πάλιν ἀνεχώρει καὶ ἐξερχόμενος ἔμενεν εἰς τὸν προειρημένον τόπον τοῦ ναοῦ τοῦ Διός.
Ὅτε λοιπὸν διέτριβεν ὁ Αὐξίβιος εἰς ἐκεῖνον τὸν τόπον, ὁ Ἀπόστολος Μάρκος ἐκήρυττεν εἰς τὴν Ἀλεξάνδρειαν τὸ Εὐαγγέλιον τοῦ Χριστοῦ καὶ ἀφ’ οὗ ἐπίστευσαν πολλοὶ καὶ ἐβαπτίσθησαν, ἀνεχώρησεν ἐκεῖθεν διὰ νὰ ζητήσῃ τὸν Ἀπόστολον Παῦλον· καὶ εὑρὼν αὐτὸν καὶ προσκυνήσας τὸν ἐδέχθη ὁ Παῦλος μετὰ χαρᾶς μεγάλης. Ὁ Μάρκος τότε τοῦ διηγήθη τὰ περὶ τοῦ Ἀποστόλου Βαρνάβα καὶ πῶς ἐτελείωσε τὸν δρόμον τὸν καλὸν μαρτυρήσας εἰς τὴν Σαλαμῖνα τῆς Κύπρου. Ἔμεινε λοιπὸν ὁ Μάρκος μὲ τὸν Παῦλον ἕως τὸν καιρὸν τῆς τελευτῆς του. Ὅτε δὲ ἔμαθεν ὁ θεῖος Παῦλος τὸν μαρτυρικὸν θάνατον τοῦ Ἀποστόλου Βαρνάβα καὶ ὅτι δὲν ἦτο εἰς τὴν Κύπρον κανεὶς ἀπὸ τοὺς Ἀποστόλους, διὰ νὰ κηρύττῃ τὸ Εὐαγγέλιον τοῦ Χριστοῦ, ἀπέστειλε τοὺς Ἐπαφρᾶν καὶ Τυχικὸν καὶ ἄλλους τινὰς πρὸς τὸν Ἡρακλείδην, τὸν Ἀρχιεπίσκοπον τῆς Κύπρου, γράψας πρὸς αὐτόν, ὅπως καταστήσῃ τὸν Ἐπαφρᾶν Ἐπίσκοπον εἰς τὴν Πάφον καὶ τὸν Τυχικὸν εἰς τὴν Νεάπολιν καὶ εἰς ἑκάστην πόλιν ἄλλους, νὰ ἀναζητήσῃ δὲ εἰς τὴν πόλιν τῶν Σολίων καὶ Ρωμαῖον τινὰ ὀνόματι Αὐξίβιον, τὸν ὁποῖον νὰ ἐγκαταστήσῃ εἰς τοὺς Σόλους, ἀλλὰ νὰ μὴ τὸν χειροτονήσῃ Ἐπίσκοπον, διότι εἶχε χειροτονηθῆ πρότερον ὑπὸ τοῦ Ἀποστόλου Μάρκου. Εὐθὺς ὡς ἔλαβε τὰ γράμματα τοῦ θείου Παύλου ὁ μακάριος Ἡρακλείδης καὶ ἀνέγνωσεν αὐτά, ἀμέσως, ἄνευ ἀργοπορίας, ἐξετέλεσεν ὅσα τὸν ἐπρόσταζεν.