Paulus dari Tarsus
itu mengacu pada era Pompian, berarti sama dengan tahun 37 M, sehingga pertobatan Paulus terjadi pada tahun 34 (T. E. Mionnet, Description des medailles antiques greques et romaines, V, 284f.)."
Dalam Surat Galatia, Paulus juga menceritakan bahwa 14 tahun setelah pertobatannya (tahun 48 M) ia masuk kembali ke Yerusalem (). Tidak diketahui sepenuhnya apa yang terjadi selama 14 tahun ini, karena Kisah Para Rasul maupun Surat Galatia tidak memberikan detail jelas. Pada akhir masa ini, Barnabas pergi untuk mencari Paulus di Tarsus dan membawa dia kembali ke Antiokhia ().
Ketika bencana kelaparan terjadi di Yudea, diduga sekitar tahun 45-46 atau 48 M, Paulus dan Barnabas berangkat ke Yerusalem untuk memberikan dukungan finansial dari komunitas Antiokhia. Menurut Kisah Para Rasul, Antiokhia menjadi pusat alternatif bagi penyebaran orang Kristen setelah kematian Stefanus. Di Antiokhialah para pengikut Yesus pertama kali disebut "Kristen"
Penulis Kisah Para Rasul menyusun perjalanan Paulus menjadi tiga perjalanan terpisah. Perjalanan pertama, (Kis. 13-14) awalnya dipimpin oleh Barnabas, yang mengambil Paulus dari Antiokhia menuju Siprus kemudian Asia Kecil (Anatolia) selatan, dan kembali ke Antiokhia. Di Siprus, nama Yunani "Paulus" mulai dipakai menggantikan nama Yahudi "Saulus". Di sini ia memarahi dan membutakan
mata Elimas si penyihir () yang berusaha menghalang-halanginya menyampaikan ajaran-ajaran mereka. Dari titik ini, Paulus digambarkan sebagai pemimpin kelompok. Antiokhia dilayani sebagai pusat kekristenan utama dari penginjilan Paulus.
Kebanyakan sarjana setuju bahwa pertemuan penting antara Paulus dan jemaat di Yerusalem terjadi di antara tahun 48-50, yang dijelaskan dalam Kis. 15:2 dan biasanya dilihat sebagai peristiwa yang sama dengan yang disebutkan oleh Paulus dalam Galatia 2:1. Pertanyaan kunci yang diajukan adalah apakah non-Yahudi yang bertobat perlu disunat. Pada pertemuan ini, Petrus, Yakobus (saudara Yesus Kristus), dan Yohanes menyetujui misi Paulus bagi bangsa-bangsa lain.
Meskipun perjanjian dicapai pada Konsili Yerusalem sebagaimana yang dipahami oleh Paulus, Paulus menceritakan bagaimana ia kemudian di depan umum mengkritik Petrus, atas keengganan Petrus untuk makan bersama dengan orang Kristen non-Yahudi di Antiokhia, setelah menerima kunjungan orang-orang Yahudi Kristen (karena secara tradisi, orang-orang Yahudi dilarang makan bersama orang-orang bukan Yahudi).
Di dalam Surat Galatia, yang merupakan sumber utama dari insiden di Antiokhia ini, Paulus mencatat perkataannya kepada Petrus: "Jika engkau, seorang Yahudi, hidup secara kafir dan bukan secara Yahudi, bagaimanakah engkau dapat memaksa saudara-saudara yang tidak bersunat untuk hidup secara Yahudi?" (). Paulus juga menyebutkan bahwa bahkan Barnabas (rekan seperjalanannya hingga saat itu) ikut-ikutan bersikap seperti Petrus.
Hasil akhir dari insiden tersebut masih belum jelas. "The Catholic Encyclopedia" menyatakan: "catatan Paulus atas insiden itu tidak meninggalkan keraguan bahwa Petrus melihat kebenaran dari teguran itu." Setelah kejadian itu Paulus kemudian berangkat memulai misi berikutnya dari Antiokhia.
Dalam perjalanan misi kedua, setelah pertikaian dengan Barnabas karena persoalan Yohanes Markus, Paulus ditemani oleh Silas. Mereka berangkat dari Antiokhia, menuju Siria dan Kilikia, dan tiba di selatan Galatia. Di Listra, Timotius bergabung dengan mereka. Mereka menyeberangi daerah Frigia dan perbatasan Misia. Lalu mereka bergabung dengan Lukas di Troas. Dia memutuskan untuk pergi ke Eropa, dan di
Makedonia ia mendirikan komunitas Kristen pertama Eropa: Jemaat Filipi. Juga di Tesalonika, Berea, Atena dan Korintus. Dia tinggal selama 1.5 tahun di Korintus, di rumah sepasang suami-isteri, Akwila dan Priskila (). Masa tinggalnya ini bersamaan dengan waktu Galio menjabat singkat sebagai gubernur (prokonsul) di Akhaya dari 1 Juli 51 sampai 1 Juli 52. Pada musim dingin tahun 51, ia
menulis surat pertama kepada Jemaat Tesalonika, dokumen tertua dari Perjanjian Baru. Tahun berikutnya ia kembali ke Antiokhia.
Setelah tinggal di Antiokhia beberapa saat, Paulus pergi ke Galatia dan Frigia untuk mendukung gereja-gereja yang telah ia dirikan pada perjalanan sebelumnya (). Kemudian ia berkeliling pada wilayah barat Bitinia dan tiba di Efesus dengan perjalanan darat. Di Efesus ia menulis surat pertamanya kepada orang-orang Korintus pada tahun 54 dan surat kedua pada akhir 57.
Setelah tiga tahun di Efesus, Paulus kemudian mengunjungi Asia Kecil dan Yunani. Kemudian mendahului Lukas, ia berlayar ke Troas, disertai beberapa murid-muridnya (), disebabkan karena rencana pembunuhan terhadap dirinya oleh orang-orang Yahudi. Dan akhirnya ia kembali ke Yerusalem dan bertemu dengan Yakobus di sana. Paulus tiba di Yerusalem
tahun 57 membawa uang sumbangan yang dikumpulkan untuk jemaat di sana dari kota-kota yang dikunjunginya. Ia disambut hangat, tetapi juga ditanya dengan teliti oleh Yakobus mengenai tuduhan bahwa ia "mengajar semua orang Yahudi yang tinggal di antara bangsa-bangsa lain untuk melepaskan hukum Musa, sebab engkau mengatakan, supaya mereka jangan menyunatkan anak-anaknya dan jangan hidup menurut adat istiadat" Yahudi.
Tidak berapa lama setelah sampai di Yerusalem, Paulus ditangkap dengan tuduhan membawa orang-orang bukan Yahudi ke dalam Bait Allah. Paulus dibawa ke markas tentara Romawi dan dihadapkan kepada gubernur Romawi Antonius Feliks di Kaisarea. Ia ditahan selama 2 tahun, sampai gubernur yang baru, Perkius Festus, membuka kembali kasusnya pada tahun 59. Karena tidak mau
diadili di Yerusalem, Paulus menyatakan banding kepada Kaisar, sehingga kemudian ia dikirim ke Roma dengan naik kapal.
Kisah Para Rasul mencatat perjalanan Paulus ke Roma, termasuk kisah terdamparnya kapal yang membawa Paulus di pulau Malta, dimana ia bertemu dengan Publius dan penduduk pulau itu yang menyambut mereka dengan ramah. Setelah 3 bulan di sana, Paulus berangkat lagi dan tiba di Roma tahun 60. Ia tinggal selama 2 tahun dalam tahanan rumah.() Seluruhnya, Paulus menghabiskan 5.5 sampai 6 tahun dari masa pelayanannya sebagai orang tahanan di dalam penjara.
Irenaeus, bapa gereja pada abad ke-2, mencatat bahwa Petrus dan Paulus adalah tokoh-tokoh utama gereja di Roma dan mereka telah menunjuk Linus sebagai uskup gereja Roma, meneruskan tugas mereka. Paulus bukan uskup gereja di Roma, tampaknya juga bukan perintisnya, karena sudah ada orang-orang Kristen di Roma ketika Paulus tiba () dan Paulus juga menulis surat kepada jemaat di Roma
sebelum ia sempat mengunjungi Roma (;). Namun, Paulus dapat berperan penting dalam mengorganisir dan membesarkan gereja mula-mula di Roma.
Paulus secara sah memiliki kewarganegaraan Romawi dari sejak lahir (). Kemungkinan besar kewarganegaraan ini diberikan kepada keluarganya karena pengabdian orang tua atau leluhurnya kepada pemerintah Romawi.
Kisah Para Rasul juga mencatat bahwa ketika Paulus diadili oleh Perkius Festus, ia menuntut naik banding kepada Kaisar (). Hanya yang berkewarganegaraan Romalah yang bisa naik banding langsung kepada Kaisar. Karena naik banding itu, ia dikirim ke Roma.
Surat-surat Paulus merupakan alat komunikasi antara dirinya dengan komunitas-komunitas Kristen perdana, tetapi juga penting karena berisi uraian teologisnya. Ada 13 surat dalam Perjanjian Baru yang menunjukkan Paulus sebagai penulisnya. Namun, saat ini sejumlah para ahli Perjanjian Baru berdebat menentukan mana surat yang ditulis sendiri oleh Paulus (surat-surat "Pauline") dan
mana surat yang mengatasnamakan dirinya sebagai penulis (surat-surat "Deutero-Pauline"). Konsensus yang sementara ini diterima di kalangan para ahli Perjanjian Baru mengenai surat-surat Paulus adalah sebagai berikut: Pengajaran Paulus yang nyata dalam surat-suratnya mendapat pengakuan positif dari Petrus yang menggolongkannya ke dalam tulisan-tulisan Kitab Suci, seperti tertulis dalam Surat 2 Petruspasal 3: