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