大马士革的长官，受了犹太人的唆使，下令要逮捕保罗。他的朋友就在夜间用筐子把他从城墙上吊下去。有三年的时间，他都在阿拉伯的小村里传讲基督。后来他回到耶路撒冷，获得了彼得的宽恕及友谊，并与他同住了一阵子。大多数的使徒均不太信任他，唯有一位初信基督的巴拿巴（Barnabas）伸出热忱的手欢迎他，并且说服耶路撒冷的教会将传讲天国福音的使命托付给这位原是逼迫教会的保罗。于是保罗传福音给那些说希腊话的犹太人，他们却想法子要杀他。使徒们或许是害怕他的过分热心会危及其他使徒，于是把他送到塔尔苏斯。
于是有八年的时间，历史上没有关于他在塔尔苏斯的记载。也许再一次地，他感觉到流行于希腊人中的神秘救世神学的影响力。后来巴拿巴找到他，请他帮忙协助在安条克的教会。他们一起工作了一年的工夫（约公元43—44年），使得许多的人相信了基督，而安条克很快就成为所有城市中基督徒最多的一座城。在那里，他们首次以“信徒”“门徒”“弟兄”或“圣徒”互称，同时也被异教徒或许带有轻蔑意味地称为基督徒（Christianoi），意即“弥赛亚”或“受膏者的门徒”。同时外邦人也是在这个地方，第一次接受新的信仰。其中有许多是敬畏神的尊贵的妇女，她们早已接受犹太的一神论及某些仪式。
安条克的信徒，不像在耶路撒冷的信徒那样贫穷。少数的人属于商人阶级，由于对传福音的热心，他们积蓄了一笔款子，作为传福音之用。教会的长老“按手在”巴拿巴和保罗的头上，就打发他们出去。历史上忽视了巴拿巴而称此次行程为“圣保罗的第一次布道旅行”（约公元45—47年）。他们坐船到了塞浦路斯，在这个岛上做了非常成功的布道。又由帕福斯（Paphos）乘船到潘菲利亚的佩尔加（Perga），然后经过极其危险的山路，到了皮西迪亚的安条克，这里的会堂非常欢迎他们。但是当他们也对外邦人传道时，那些自认为正统的犹太人开始唆使城内有名望的人将保罗和巴拿巴逐出境外。在以哥念，他们也遭遇同样的困难。在里斯特拉，犹太人甚至用石头打保罗，并将他拖到城外，听任其死。但是，保罗和巴拿巴仍然“充满了圣灵的喜乐”，又往德尔菲，对那城里的人传福音。然后他们沿着原路线回到佩尔加，又行船至叙别亚的安提阿。在这里，他们面临一个基督教历史上最重要的问题。
原来耶路撒冷一些为首的门徒，听说保罗和巴拿巴接受了外邦信徒，而未要求他们受割礼，于是赶到安条克来“教训弟兄们说，你们若不按摩西的规条受割礼，不能得救”。对犹太人而言，割礼不仅是洁净的仪式，主要是象征古时犹太民族与神所立的约。所以这些犹太籍的基督徒，均为违背此约的想法所震惊。而保罗和巴拿巴也深知这些从耶路撒冷来的密使若是得胜的话，基督教永远不可能为大多数外邦人所接受。那么，正如海涅所言，基督教将沦为犹太人的“异端邪说”，迟早也会自灭的。于是他们两人回到耶路撒冷（约公元50年），为这件事与使徒和长老们辩论，当时几乎所有的使徒与长老仍只在殿中敬拜神，结果雅各勉强地同意了保罗与巴拿巴的意见。最后达成协议：归服神的外邦人，只要禁戒污秽和奸淫以及食用作为牺牲的或勒死的牲畜。很明显，保罗是以答应用安条克教会的金钱去支持耶路撒冷的贫穷教会作为条件，才达成这项协议的。
然而这个问题太重要了，并没有轻易被放过。于是又有第二批正统的犹太基督徒由耶路撒冷到安条克，发觉彼得与外邦人一同吃饭，便劝服他离开那些未受割礼的外邦人，而与犹太籍的基督徒在一起。我们不知道对于这件事彼得到底是站在哪一边，不过保罗告诉我们，在安条克，“他当面抵挡彼得”，并且指责他的虚伪。也许彼得只不过希望像保罗一样，“对什么人就做什么事”。
在保罗50多岁的时候，他开始了第二次宣教旅行。这次他与巴拿巴有了争执，以后巴拿巴留在他的故乡塞浦路斯，而不再在历史上出现了。保罗再一次访问小亚细亚各教会，并且在里斯特拉挑选了一位年轻的门徒提摩太（Timothy），于是保罗终于找到一位自己渴望已久、热切爱护的对象。他俩一同经过弗里吉亚和加拉提亚一带，最远到达北方亚历山大的特洛阿斯（Troas）。在这里，保罗结识了路加，一位未受割礼的外邦信徒，他聪明睿智，心地善良，也许就是第三本福音书及《使徒行传》的作者。他们俩似乎有意要缓和基督教从一开始就有的争执。从特洛阿斯，保罗、提摩太以及西拉航行至马其顿，这是他们第一次到达欧洲。保罗和西拉在菲利皮——安东尼曾征服布鲁图的地方——以扰乱安宁秩序的罪名被捕，受鞭笞，并遭逮捕而入狱，但因他们是罗马公民而被释放。然后保罗和西拉来到帖撒罗尼加，一连三个安息日，在那里的会堂对犹太人传道。少数人因此相信，并且开始组成教会；其余不信的人，唆使全城来抵挡保罗，说他宣称另有一个王。他的朋友于是在夜间打发他们两人到比罗阿（Beraea），这个地区的人非常渴慕接受传道。但是帖撒罗尼卡的犹太人又往比罗阿去，公开指责保罗是犹太教的敌人。于是保罗沮丧而孤单地往雅典航行（约公元51年）。
在这个异教、科学、哲学的中心，保罗发觉自己非常孤单无靠。仅有少数的犹太人听他讲道；而他必须站在市场的地方，大声疾呼着与其对手争取听众。有些听众与他争辩；有些人嘲笑他说：“看看这个捡破烂的家伙，到底想要证明什么？”也有不少人对他所说的很感兴趣，于是把保罗带到阿雷奥帕古斯，以便安静地听讲。保罗告诉他们说，他在雅典的时候看见一座祭坛，上面写着“未识之神”；这可能是捐赠者对某个不知名的神的帮助表达谢意。保罗则认为这是承认他们对神的无知。然后保罗又口若悬河地说道：
那些你们不认识而敬拜的，我现在告诉你们。创造宇宙和其中万物的上帝……不住人手所造的殿……将生命、气息、万物赐给万人……他从一人造出万族的人……要叫他们寻求上帝，或者可以揣摩而得。其实他离我们各人不远。我们生活、行动、存留，都在乎他，就如你们作诗的所说 ……我们既是神所生的，就不该以为上帝的神性，像人用手艺、心思所雕刻的金、银、石。世人蒙昧无知的时候，上帝并不鉴察，如今却吩咐各处的人都要悔改，因为他已经定了日子，要借他所设的人，按公义审判天下，并且叫他从死里复活，给万人作可信的凭据。
保罗企图调和基督教与希腊哲学，这委实是种大胆的尝试，然而受他影响而改变的人极少。雅典人因为听了太多的道理，对任何道理均不热衷，于是保罗很失望地离开了雅典往哥林多去了。哥林多这个地方，聚集了许多从商的犹太人，保罗在这里停留了18个月（约公元51—52年），平时以织帐篷为生，安息日则到会堂讲道。那些忧虑不安的犹太人又到罗马迦流（Gallio）面前控告保罗，指控他“劝人不按《律法》敬拜上帝”。迦流回答说：“所争论的，若是关乎言语、名目和你们的《律法》，你们自己去办吧！这样的事，我不愿意审问。”就把他们撵出公堂。众人便揪住管会堂的，在堂前打他，“这些事迦流都不管”。保罗传福音给在哥林多的外邦人，其中有许多人都接受。对这些人而言，基督教与他们以往所接受的关于神秘信仰所提到的复活救主的信息大同小异，而保罗也受到不少的影响，按希腊人所熟悉的说法，将基督教介绍给希腊人。
约公元53年，保罗由哥林多回到耶路撒冷，向教会问安，然后很快开始了第三次的布道旅行，访问了安条克和小亚细亚的教会，并且以他的热忱与信心来巩固众教会。保罗在艾菲索斯住了两年，并且行了些非常的奇事。因此许多人视他为行神迹的人，甚至有人从保罗身上拿手巾或围裙放在病人身上，病就好了。也许保罗在艾菲索斯也曾告诉他们不要拜人手所做的偶像，致使阿尔忒弥斯神庙中制造偶像的生意大受影响。有一个银匠名叫德米特里（Demetrius），是制造阿尔忒弥斯女神银龛的，聚集了同行的工人，起来闹事抵挡保罗及他所传的道。于是满城都骚动起来，众人受了德米特里的鼓动，大声喊着说：“大哉！艾菲索斯人的阿尔忒弥斯啊！”如此约两小时之久，直到后来这城里的官员安抚众人，才把众人解散了。这事以后，保罗更有勇气，前往马其顿。
他在他所建立的菲利皮、帖撒罗尼卡及比罗阿教会度过了一段非常愉快的日子。当他听到哥林多的教会被纷争与淫乱之事搅扰时，不仅写信去责备他们，并且亲自到哥林多教会（约公元56年）当面质问诽谤他的人。那些人指责保罗以传道谋利，讥笑他所见的异象，并且重新要求所有基督徒必须遵守犹太的《律法》。保罗一再提醒那些骚动的众人，无论在何处，他均以双手谋生。至于说到一些物质上的供应，难道说他没有为传福音而受苦吗？——8次被鞭笞，1次惨遭石击，3次船舶遇难，还有成千次遭遇到强盗、激进分子及种种的危险。这些人的扰乱言语，导致了那些坚持外邦人必须受割礼的犹太人集团的死灰复燃，于是破坏了耶路撒冷协定，并且也搅扰了加拉提亚教会，要求他们遵行全《律法》。于是保罗写了一封很气急的信给加拉提亚人，信中表示他与皈依犹太教的基督徒完全决裂，宣称“人得救，并不是靠遵守《律法》，乃是信耶稣基督是永生上帝的儿子”。然后，他返回耶路撒冷，想在众使徒前为自己辩护，并且期待着在圣城庆祝五旬节，然而却不知有什么更大的磨难正等待他。他希望能从耶路撒冷到罗马，甚至到西班牙，一直不停地传道，直到罗马帝国每一个省份都听到天国的福音，及复活基督的应许。
