Ο Μάρκος, συνοδεύοντας τον Βαρνάβα, περιόδευσε μαζί του δυο φορές ολόκληρη την Κύπρο. Την πρώτη φορά, άνοιξη του 45, στην αποστολή μετείχε ο απόστολος Παύλος. Την δεύτερη φορά, το 49, την αποστολή που περιόδευσε και πάλι ολόκληρη την Κύπρο, αποτελούσαν μόνο οι Βαρνάβας και Μάρκος.
Βλέπε λήμμα: Απόστολος Βαρνάβας
Κατά την πρώτη περιοδεία, οι Παύλος, Βαρνάβας και Μάρκος ξεκίνησαν από την Αντιόχεια, πήγαν στη Σελεύκεια κι από εκεί ταξίδευσαν με καράβι στην Κύπρο. Αποβιβάστηκαν στη Σαλαμίνα όπου δίδαξαν αρχικά σε συναγωγές Ιουδαίων. Στη συνέχεια δίδαξαν παντού, διελθόντες τήν νῆσον ἄχρι Πάφου (Πράξεις, 13,5). Από το νησί αναχώρησαν με καράβι που απέπλευσε από την Πάφο, και πήγαν στην Πέργη της Παμφυλίας. Εκεί ο Μάρκος δείλιασε και απεχώρησε, επιστρέφοντας στα Ιεροσόλυμα, ενώ οι Παύλος και Βαρνάβας συνέχισαν το ιεραποστολικό τους έργο διδάσκοντας και ιδρύοντας χριστιανικές κοινότητες σε διάφορες πόλεις (Πέργη, Αττάλεια, Αντιόχεια, Ικόνιον, Λύστρα, Δέρβη κ.α.).
Όταν, ύστερα από τέσσερα χρόνια, ο Παύλος σχεδίασε νέα επίσκεψή του στις ιδρυμένες ήδη Εκκλησίες, ο Βαρνάβας πρότεινε να πάρουν μαζί τους και τον Μάρκο. Ο Παύλος αρνήθηκε να συνεργαστεί με τον Μάρκο και οι δυο απόστολοι χώρισαν. Ο Παύλος συνέχισε αλλού το έργο του, ενώ στην Κύπρο απεφασίσθη να έλθουν ξανά ο Βαρνάβας και ο Μάρκος. Ξεκίνησαν από την Αντιόχεια για τη Λαοδίκεια κι απ' εκεί, με καράβι, ήλθαν στην Κύπρο. Αποβιβάστηκαν στον Κορμακίτη και, στη συνέχεια, επισκέφθηκαν όλες σχεδόν τις μεγάλες πόλεις του νησιού: Λάπηθο, Σόλους, Ταμασσό, Πάφο, Κούριον, Αμαθούντα, Κίτιον και Σαλαμίνα. Σε όλες αυτές τις πόλεις είτε έγιναν δεκτοί με εχθρότητα από τους Εβραίους κατοίκους τους, είτε δεν μπόρεσαν να διδάξουν επειδή γίνονταν μεγάλες ειδωλολατρικές τελετές. Όμως σε διάφορα μέρη της Κύπρου συνάντησαν Χριστιανούς, τους οποίους γνώριζαν από την πρώτη περιοδεία, ενώ προσηλύτισαν στη νέα θρησκεία και αρκετούς άλλους, συστήνοντας και επισκοπές. Κατά την περιοδεία τους στις κυπριακές πόλεις συνοδεύονταν και από μερικούς Κυπρίους Χριστιανούς όπως ο Τίμων, ο Ηρακλείδιος, ο Ρόδων και ο Αρίστων.
Στη Σαλαμίνα ο Βαρνάβας βρήκε μαρτυρικό θάνατο από τους Εβραίους της πόλης αυτής. Αναζητήθηκε επίσης και ο Μάρκος, αλλά αυτός κατόρθωσε να διαφύγει και να σωθεί. Λίγο πιο ύστερα, βοηθούμενος από τους Τίμωνα και Ρόδωνα, ο Μάρκος κατόρθωσε να βρει το λείψανο του Βαρνάβα και να το θάψει κάπου κοντά στη Σαλαμίνα. Τελικά όμως έγινε αντιληπτός και καταδιώχθηκε μέχρι τις Λέδρες (Λευκωσία).
Βλέπε λήμμα: Λέδραι
Εκεί παρέμεινε για τρεις μέρες κρυβόμενος σε μια σπηλιά και στη συνέχεια, μαζί με τους Τίμωνα, Αρίστωνα και Ρόδωνα, διέφυγε προς τα δυτικά του νησιού. Στον Λιμνίτη ο Μάρκος συνάντησε τον Αυξίβιο που τον κατήχησε στον Χριστιανισμό και τον χειροτόνησε πρώτο επίσκοπο της πόλης των Σόλων. Στον Λιμνίτη, τέλος, βρήκε ένα αιγυπτιακό καράβι, στο οποίο και επιβιβάστηκε για την Αλεξάνδρεια (Acta Barnabae, 22-26).
Πηγή
Μεγάλη Κυπριακή Εγκυκλοπαίδεια