保祿在厄弗所時得知有些安提約基雅的猶太裔基督徒探訪他所創立的迦拉達團體時，告訴他們必須接受割損對此他感到十分震驚。他在給迦拉達人的信中強烈譴責他們即使有這種想法也不應該（迦3:1-3）。割損是天主與亞巴郎所訂立盟約時的標記。保祿曾教導這些外邦人基督徒救恩來自信德，而非來自遵守梅瑟法律。他告訴他們並不需要割損。他們屬於亞巴郎及可以繼承盟約全因他們是屬於基督。與基督的盟約並不需要割損。事實上，保祿說：「若你們還願意受割損，基督對你們就沒有什麼益處。」（迦5:2）
保祿第二次出外傳教時在格林多遇到並住在阿桂拉和他的妻子普黎史拉那裏。他們二人是被逐出羅馬的猶太人。保祿在格林多住了約一年半，期間以製造帳幕謀生和傳揚福音。路加說保祿在那裏皈化了多人，包括會堂長克黎斯頗。保祿自己記得克黎斯頗是他在格林多所施洗的幾位人士之一，並說：「基督派遣我，不是為施洗，而是為宣傳福音」（格前1:17）。我們不能斷定保祿認為洗禮並不重要，可能他認為他的工作是播種，由別人去收割成果。保祿認為自己是一位傳教士。
保祿以厄弗所作為基地，向周圍的地域展開傳教工作。其中一個城市是在厄弗所以東約一百二十英里的哥羅森。哥羅森的初生基督徒團體應是保祿的門徒厄帕夫辣所創立的。我們對厄帕夫辣的認識很少，但保祿稱他為「親愛的同僕」（哥1:7）和「為基督耶穌與我一同被囚的厄帕夫辣」（費23）。保祿明認哥羅森人因厄帕夫辣的福傳而得到天主的恩寵，並稱他「是基督的忠信僕役，也就是他給我們報告了聖神所賜與你們的愛。」（哥1:7-8）雖然保祿自己明顯地已是一股強大的福傳動力，他卻有一班伙伴從旁協助，這包括巴爾納伯、弟茂德、息拉、路加、若望馬爾谷、弟鐸、索斯特乃及厄帕夫辣等人。
在塞浦路斯島時，保祿在帕佛市遇見一名術士，取了罕有的名字巴爾耶穌。宗13:6指喻他為「猶太人假先知」。他受僱於島上羅馬總督色爾爵保祿，這官長被路加描述「是個聰明人」。色爾爵邀請了巴爾納伯和掃祿來，欲想理解他們為何訪臨塞浦路斯，以及他們在當地猶太人會堂的教誨。身為地方總督的「議會賢士」和私人「教士」的巴爾耶穌反對這兩位傳教士，顯然是擔心色爾爵被福音所感召，導致他（巴爾耶穌）失業。保祿譴責巴爾耶穌並聲稱他為「魔鬼的兒子，一切正義的仇敵」，又使他變成瞎子。色爾爵保祿目睹自家術士的遭遇後，大為感動，終接受了保祿的教誨而成為信徒。
路加在《宗徒大事錄》中記述保祿在被押往羅馬的航程中，從海難中死裡逃生，發現自己漂流到馬爾他島上 (宗28:3) ，受到當地人友善的款待。但當保祿坐在營火旁，有一條毒蛇纏住並咬了保祿的手，他們見狀就認定保祿犯了罪且要被懲罰。他們預計保祿會發腫然後死去；但等了很久，保祿依舊安然無恙，島上的人開始認為保祿是神。在《宗徒大事錄》中，路加暗指自己是旅程的同行者。或許因他目睹保祿這事，而驅使他要在褔音中記下耶穌的話語：「看，我已經授予你們權柄，使你們踐踏在蛇蠍上，並能制伏仇敵的一切勢力，沒有什麼能傷害你們。」(路10:19)。保祿曾多次面對死亡但每次都否極泰來，他深信這是耶穌基督賦予的神能。
保祿在公元51年抵達雅典，雖然雅典的光輝歲月已過，畢竟還是一個文化和智慧之都。當保祿在市中心向聚集的人群宣講耶穌基督的復活時，卻被斯多噶和伊壁鴆魯兩派的哲學家質疑。這些知識份子遂邀請保祿到阿勒約帕哥(一個離城不遠的壯麗小丘)，去解釋他所說新奇的事。正當保祿開始向在場人士講述耶穌從死者中復活了的事蹟時，那些人感覺毫無新意而變得焦躁不安，一個接著一個離開去了。保祿嘗試將耶穌與雅典人敬畏的「未識之神」拉上關係，縱使當中有少數人 信從歸化了（參 宗17），這策略的成效卻不大。若然保祿能成功地游說雅典人皈依成為基督徒，他理應致書雅典信眾。即使保祿 真的撰寫了雅典書，這書信並沒有被保存下來。
學者認為，保祿納入了初期基督徒的讚美詩或詩歌在他的書信裏。最顯著的例子可見於斐2。保祿鼓勵團體團結合一，應效法耶穌行謙遜。他運用詩歌式的風格或文體來表達： 「衪貶抑自己，聽命至死，且死在十字架上」以及「致使上天、地上和地下的一切，一聽到耶穌的名字，無不屈膝叩拜。」（斐2:6-11）。猶太裔基督徒熟悉這些詩歌，並由此而形成希伯來讚美詩。
在厄弗所，保祿鼓勵基督徒要充滿聖神，以聖詠、詩賦及屬神的歌曲，互相對談(弗5:19)。這可料想，保祿應是借助了詩歌來豐富他的文學作品，好能啟迪其讀者。
保祿對初期教會那強而有力的影響可從《保祿大事錄》一書中得以證實。該書的作者是一位虔誠的小亞細亞基督徒長老。天主教會認為該書欠缺正統性及認受性，因而將之定為偽經。書的作者這樣描繪保祿的外貌：「身材矮小、近乎禿髮、彎彎的腿．．．深鎖的眉及彎曲的鼻樑．．．」。他認為保祿有時像天使！作者將焦點放在保祿所關心的貞潔及獨身生活上。保祿說過已婚的人如避免行房、有妻子的，要像沒有一樣、而那些保持童貞的都蒙祝福。根據《保祿大事錄》記載，一名叫德克拉(Thecla)的貞女原已訂婚，但當她聽了保祿的教導後就馬上解除了婚約；她的母親非常憤怒，更要求一位法官燒死她的女兒！