На основе этого сообщения развернут целый рассказ о том, как Марк отправился искать апостолов, как он нашел Павла больным и гневающимся на него за то, что тог отстал от них. Ярко показано стремление Марка заслужить прощение Павла. Марк раскаивается, просит на коленях прощения у Павла, издали наблюдает, как Павел и Варнава поучают новообращенных. Но Павел остается непреклонным. Реальный автор апокрифических Деяний вырисовывает живые характеры — жесткий, не идущий на компромиссы Павел, который, по существу, поступает не по христиански, не желая принять раскаяние Иоанна Марка. Тот же, наоборот, показан искренне кающимся на коленях у ног сурового апостола. Павел ни при каких условиях не пожелал взять с собой Марка в дальнейшие странствия. Он сумел настроить против Марка и других своих спутников, которые также возражают против участия Марка. Кто эти люди — неясно, поскольку в путешествие, согласно каноническим Деяниям, Павел берет только Силу. Вероятно, автор ввел этих неназванных «других» для усиления конфликта. Варнава, прежде верный спутник Павла, заступается за Марка, поскольку он помогал им на Кипре во время их благовествования. Но Павел не уступил и Варнаве. И только после видения во сне Павел решил не препятствовать Варнаве идти вместе с Иоанном Марком на Кипр, но уже без него. Позиция Павла вряд ли могла вызвать сочувствие у читателя, хотя Павел и Варнава перед разлукой как бы примиряются, но теплые слова вложены в уста Варнавы.
Описание конфликта представляет собой своеобразную вставную новеллу, разукрашивающую, как это делалось и в некоторых других деяниях, сообщения Деяний новозаветных. Мельком упомянут в апокрифе еще один повод для гнева Павла:
у Марка в Памфилии находились какие-то пергаментные рукописи, но что это такое, не раскрыто, поскольку автор апокрифа, вероятно, не смог сконструировать их название, а добавить мотив для отказа Павла простить Марка, по-видимому, он счел необходимым.
Дальнейшее повествование Деяний существенно отличается от рассказа о раскаянии Марка. Оно построено как путевой дневник, где перечисляются населенные пункты, через которые проходили Варнава и его спутники (кроме Иоанна Марка к путешественникам присоединялись по дороге еще отдельные люди). Интересно отметить, что проповедники почти не учили в городах, где было много языческих святилищ; они получали приют, главным образом, в деревнях. В отличие от большинства поздних деяний, Варнава не разрушает эти святилища, не уничтожает идолов, а только «отрясает прах со своих ног», уходя от них подальше. Единственное чудо возмездия, которое совершает Варнава, это осуждение процессии (священного бега) обнаженных мужчин и женщин, которые после его проклятий попадали и даже некоторые умерли. Варнава совершает и исцеления. В этом апокрифе упоминается исцеление с помощью Евангелия от Матфея, которое Варнава накладывает на больного. По словам автора «Деяний Варнавы», апостол получил это Евангелие от самого Матфея. Реально это Евангелие было написано позже возможных путешествий Варнавы. У Павла нет сведений о существовании евангельских текстов, у него слово «Евангелие» означает благую весть, которую проповедует и сам Павел. Почему из канонических Евангелий выбрано именно Евангелие от Матфея, обладающее чудодейственной силой, сказать трудно; скорее всего Евангелие от Матфея уже во время создания апокрифа считалось первым по порядку расположения среди книг Нового Завета и было особо почитаемым. Кроме того, если Марк Иоанн воспринимался как будущий Евангелист, то его Евангелия еще не могло существовать во время путешествий с Варнавой.
При известной модернизации событий автор апокрифа старался сохранить некоторую исторически реальную картину. К таким реалиям относятся и небольшое число спутников Варнавы, и наличие среди его последователей людей низшего статуса, например «священных рабов» (иеродулов). Иеродулы не были рабами в прямом смысле слова, это был особый юридический статус зависимых от храмов людей, некоторые из них могли жить в собственных домах, и, как это видно из рассказа апокрифа, обладали свободой передвижения.