وأخذ الرجلان يعملان معاً (٤٣ - ٤٤؟) فهديا كثيراً من الناس، فلم تلبث إنطاكية أن فاقت سائر المُدن في عدد مَن بها من المسيحيين. وفيها أطلق الوثنيون إلى "المؤمنين"، أو "التلاميذ" أو "القدّيسين" كما كانوا يسمون أنفسهم اسم الكرستيانوي أي أتباع المسيح أي الإنسان الممسوح. وهنا أيضاً انضمت "الأمم" أي غير اليهودي إلى الدين الجديد. وكان معظم هؤلاء ممن "يخشون الله" وكانت كثرتهم من النساء اللاتي آمنّ ببعض طقوس اليهودية وبما فيها من دعوة إلى الوحدانية.
ولم يكن الاخوة في إنطاكية فقراء كأمثالهم في أورشليم، فقد كانت فيهم أقلية لا بأس بها من طبقة التجّار، فاندفعوا بقوة هذه الحركة الفتية الناشئة إلى جمع قدر من المال ليستعينوا به على نشر الإنجيل، "فوضع" رؤساء الكنيسة "أيديهم" على برنابا وبولس وبعثوهما فيما يسميه التاريخ "رحلة القدّيس بولس التبشيرية الأولى"(٤٥ - ٤٧؟) وهي تسمية تستخف بشأن برنابا. وأبحر الرجلان إلى قبرص، ولقيا نجاحاً مشجعاً بين اليهود الكثيرين المقيمين في تلك الجزيرة. ثم ركبا السفينة من يافوس إلى برجا في بمفيلية واجتازا طرقاً جبلية وعرة تعرضا فيها للخطر حتى وصلا إلى إنطاكية في بسيديا Pisidia. واستمع إليهما الكنيس ورحب بهما فلما بدأ يعظان "الأمم" كما يعظان اليهود غضب عليهما اليهود المتمسكون بدينهم وحملوا موظفي البلدية على إخراج المبشرين من المدينة. ونشأت هذه الصعاب نفسها في إقونيوم Icobium، ورجم بولس في لسترا بالحجارة وجر علو وجهه إلى خارج المدينة، وتركا في العراء ظناً من أعدائه أنه مات. بيد أن قلبي بولس وبرنابا كانا لا يزالان يفيضان غبطة بروح القدس فحملا الإنجيل إلى دربي Derbe ثم عادا بالطريق نفسه إلى برجا وأبحرا منها إلى إنطاكية السوريّة، وفيها واجهتهما أعقد مشكلة في تاريخ المسيحية ذلك أن بعض التابعين الممتازين في دمشق سمعوا أن المبشرين كانا يقبلان