Apostlene startede deres mission op, og tog Markus med sig. De tog til Seleukia, og sejlede derfra til Kypern. I Salamis forkyndte de i jødernes synagoger. "De drog så gennem hele øen lige til Pafus; dér traf de en troldmand og falsk profet, en jøde ved navn Barjesus. Han opholdt sig hos statholderen Sergius der var en forstandig mand. Denne indbød Barnabas og Saulus og ønskede at høre Guds ord. Men Elimas, troldmanden (thi dette betyder hans navn), stod den imod og søgte at hindre statholderen i at komme til troen."