保羅先是在小亞細亞的一些沿海城市布道，使許多人改信了基督教。希臘人非常樂意聽他傳教。他們能領會他的說理方法。他們佩服他在說服他們所提出的異議時采取的方法，因而自然就愉快地加入了這一新教。
但是，在地中海的大多數港口城市，不少猶太基督徒小團體卻憎恨保羅，並力圖破壞他的工作。
一代又一代沿襲下來的宗教偏見，不是一朝一夕就能消除的。有些好心人認為保羅似乎走得太遠了，認為他對信希臘宙斯神和波斯太陽神的人太友好了，他應該把自己是猶太人這一點放在第一位，基督教的理想應屬第二位，而且應該盡量按照古老的“摩西十誡”辦事。
保羅費盡口舌，企圖向他們證實基督教和猶太教兩者毫無相同之處，一個人不能同時信奉耶和華和耶穌的上帝，這就使他們對保羅的厭惡變成了公開的憎恨。
他們曾有好多次試圖殺害保羅。後來保羅終於明白，基督教如果要生存下去，就必須向一批完全新的公眾呼籲，而且必須毫不含糊地毅然和猶太教一刀兩斷。
他這時，依然在小亞細亞一帶布道，但是最後到了特羅阿斯（離荷馬所歌唱的古老的特洛伊城的廢墟不遠的一個海港）時，他終於下決心到歐洲去傳教。
他穿越赫勒斯滂海峽直接去馬其頓中心的一個重要城市菲利皮。
到達了亞曆山大的故國之後，由於保羅熟知希臘語，就用希臘語向他的第一批西方聽眾宣揚耶穌的教義。
但是，他隻講了兩次就被逮捕，關進了牢房。
但是當地人民喜歡這位遠道而來的布道者，於是就偷偷地幫他逃走了。
保羅並沒有就此做縮頭烏龜，而是決定向敵人的堡壘進攻。他到雅典去。雅典人很有禮貌地聽他講道。但四個多世紀以來，雅典人已經聽了許多新的教義，因此他們對傳教士已經不感興趣。保羅講的“神”沒有任何特殊之處。
保羅的工作盡管從未受到阻撓，卻也沒有一個人出來要求施洗。
但是，保羅卻在科林斯取得很大成功，這一點在他後來寫給科林斯的教友的兩封信中我們可以知道。他在信中對他的思想作了進一步解釋，隨著時間的流逝，這些思想離猶太基督徒仍然感到非常親切的那些舊教規越來越遠了。
那個時候，保羅已經在歐洲住了好些時間。
理想的一切傳教工作的基礎已經打好，他可以回到他自己的小亞細亞家園去了。
保羅首先訪問了西海岸的以弗所。自古以來，這個城市裏就有一個狄阿娜神廟。狄阿娜（希臘人稱她為阿耳忒彌斯）是阿波羅的孿生妹妹。她不僅是月亮女神，人們認為她能對一切生物施加影響，而且在人們的想象中，她的權力甚至超過她的父親宙斯。正像中世紀時，人們普通認為耶穌的母親瑪利亞要比耶穌更值得他們尊敬那樣。
保羅對這個城市的情況不太了解，便匆忙允許他在當地的教堂講道。他雖然獲得了許可，但是以弗所的猶太人聽他講了幾次以後，又立即把這事撤銷了。於是他便租了一個以前曾是一個希臘哲學家講學的學堂。保羅在三年中在這個學堂的講道方式幾乎可以使人稱此學堂為第一個神學院。
像耶路撒冷一樣，以弗所是一個壟斷著宗教的城市。狄阿娜神廟裏的禮拜儀式使許多人富得流油。
以弗所除遊客外，還有祭品。銷售狄阿娜塑像的生意很興旺，朝聖者把塑像帶回家去，正像現在我們在羅馬買彼得的塑像和在盧爾德買聖母像相同。
要是保羅獲得成功，那麼自古以來對創造奇跡的女神的神奇力量的信仰就將遭到破壞，而上述這種買賣當然就會受到毀滅性打擊。於是金匠、銀匠和神廟的祭司們就像幾年前他們的耶路撒冷同行一模一樣地行動起來。他們想跟撒都該派殺害耶穌和法利賽派那樣，把保羅就法。
保羅被人告知這種危險，他就逃跑了。不過他的工作已經完成。
這時，以弗所的基督教團體已經發展壯大，並且強大得難以摧毀。盡管後來保羅再也沒有來此訪問，但以弗所已經成為早期基督教世界的最重要力量。有關最後確定新教義的最初幾次會議，也是在這個城市召開的，我們可從公元2世紀和3世紀的編年史中讀到這一點。