หลังจากสเทเฟนถูกหินขว้าง บรรดาคริสตชนถูกเบียดเบียนอย่างหนัก และหลายคนหนีออกจากกรุงเยรูซาเล็ม ที่เมืองอันทิโอกในแคว้นซีเรีย กลายเป็นบ้านหลังที่สองของคริสต์ศาสนา แม้แต่บุคคลที่ไม่ใช่ชาวยิวก็สนใจในความเชื่อ บารนาบัสเห็นว่าเป็นไปได้ที่จะมีการกลับใจเป็นจำนวนมาก จึงขอร้องเซาโลให้มาช่วย ทั้งสองประสบความสำเร็จอย่างมาก
ในเวลาต่อมาบารนาบัสและเซาโลเริ่มงานแพร่ธรรมสู่คนต่างชาติ เซาโลเป็นที่รู้จักในนาม เปาโล หลังจากสเทเฟนถูกหินขว้างที่กรุงเยรูซาเล็ม ชาวยิวเริ่มเบียดเบียนคริสตชน หลายคนหลบหนีไปไกลถึงแคว้นเฟนีเซีย เกาะไซปรัส และที่เมืองอันทิโอก พวกเขาเริ่มประกาศพระวาจาแก่ชาวยิวอื่นๆ และที่เมืองอันทิโอก คริสตชนบางคนประกาศข่าวดีให้แก่ชาวกรีก และคนจำนวนมากได้กลับใจ (กจ 11:19-26) พระศาสนจักรที่กรุงเยรูซาเล็มได้รับข่าวความก้าวหน้านี้ จึงตัดสินใจส่งบารนาบัสไปยังเมืองอันทิโอก บารนาบัสชื่นชมยินดีอย่างมากกับสิ่งที่ท่านเห็น และเร่งเร้าให้คริสตชนในเมืองอันทิโอกปฏิบัติกิจการดีที่กำลังกระทำอยู่ ซึ่งดูเหมือนว่าสามารถทำให้คนกลับใจเป็นจำนวนมาก แต่อันทิโอกเป็นเมืองใหญ่และต้องการคนมาช่วย บารนาบัสคิดถึงเซาโลแห่งทาร์ซัส และความสามารถมากมายในฐานะผู้เทศน์สอนข่าวดี
ดังนั้นจึงไปที่เมืองทาร์ซัสและนำเซาโลมาที่เมืองอันทิโอก ตลอดทั้งปี ทั้งสองทำงานกับกลุ่มคริสตชนที่เมืองอันทิโอก และประสบความสำเร็จอย่างมากมาย อันที่จริง ผู้ติดตามพระเยซูเจ้าถูกเรียกว่า คริสตชนเป็นครั้งแรกที่เมืองอันทิโอกนี่เอง และกลายเป็นเมืองหลวงที่สองของคริสตชน เปาโลและบารนาบัสเริ่มเทศน์สอนข่าวดีแห่งพระวรสารในภูมิภาคอื่นๆ แรกสุดพวกเขาประกาศกับชาวยิวในศาลาธรรม เป็นที่ดึงดูดใจผู้ติดตามมากมาย
และคนต่างศาสนาหลายคนมาร่วมฟังข่าวดี แต่จุดนี้เองทำให้ชาวยิวบางคนไม่พอใจ อย่างไรก็ตามเปาโลและบาร์นาบัสชี้แจงว่า ต้องเทศน์สอนประชาชนทั้งหมด ทั้งคนต่างศาสนาและชาวยิว เพราะว่าพระเป็นเจ้าทรงมีพระบัญชาให้พวกเขาเป็น "แสงสว่างส่องนานาชาติ เพื่อท่านจะได้นำความรอดพ้นไปจนสุดปลายแผ่นดิน" (กจ 13:47) บรรดาคนต่างศาสนามีความยินดีในคำกล่าวนี้ และขอบคุณพระเจ้าสำหรับข่าวดีนี้ ในระหว่างการเดินทางประกาศพระวรสารครั้งแรกนี้ เซาโลเริ่มใช้ชื่อเป็นภาษากรีกคือ เปาโล ท่านเดินทางครั้งแรกกับบารนาบัสและหลังจากนั้นเดินทางคนเดียว ท่านเริ่มลำดับการเดินทางธรรมทูตผ่านส่วนต่างๆ ของอาณาจักรโรมัน ที่ซึ่งท่านไป ท่านจะตั้งกลุ่มคริสตชนเล็กๆ และให้อยู่ในความดูแลของผู้นำที่ไว้วางใจได้ | 
