Là một người bắt bớ Kitô hữu và hãm hại Hội thánh, Phaolô gặp nhiều khó khăn khi đi rao giảng Tin Mừng Chúa Giêsu Kitô: những tiếp đón không niềm nở hay nghi kỵ của các Tông đồ, các môn đệ và Kitô hữu.

Trong thư gởi tín hữu Corintô kể về việc Chúa Kitô Phục sinh hiện ra, Phaolô nói: trước là với Kêpha, rồi với Nhóm Mười Hai. Sau đó, với hơn năm trăm anh em.. Tiếp đến, với Giacôbê, rồi với tất cả các Tông Đồ. Sau cùng... với tôi (1 Cor 15:5-8).

Với các Tông đồ, Phaolô nói đến việc Ngài gặp Phêrô, Giacôbê và Gioan trong những lần khác nhau. Sau khi gặp Chúa Giêsu trên đường Damas, Phaolô lên Giêsuralem gặp Kêphas trong 2 tuần (Gal 1:18), và gặêp Giacôbê, người anh em của Chúa (Gal 1:19). Phaolô cũng gặp Gioan, một trụ cột của Giáo hội (Gal 2:9). Không thấy Phaolô nói đến việc gặp các Tông đồ khác.

Với Phêrô, có lúc Phaolô đối chất trực diện về điều mà ông cho là Phêrô giả hình. Khi một số môn đệ của Giacôbê (có lẽ là người Do thái tin theo Chúa Kitô) gặp Phêrô ở Antiokia, Phêrô vì nể hay sợ những người Do thái này nên đã không dám ngồi ăn với những người dân ngoại (không chịu cắt bì). Phaolô trách Phêrô và những người theo ông là giả hình (Gal 2:12-14).

Phaolô gặp nhiều khó khăn khi tranh đấu dành cho mình vị thế của một Tông đồ trong việc mục vụ. 

Luca ghi lại chuyện Phaolô lên Giêrusalem để họp Công đồng liên quan đến vấn nạn truyền giáo cho dân ngoại: liệu người muốn gia nhập Giáo Hội mà không là Do thái có phải chịu phép cắt bì không? Luca kể lại trong sách Công Vụ Tông Đồ với những lời xoa dịu tình trạng căng thẳng của cuộc họp, trình bày một cuộc họp chung, công khai với những nhà lãnh đạo giáo hội: sau khi nghe Phaolô và Barnaba trình bày, Phêrô và Giacôbê lên tiếng và cả hai đồng thuận không cần cắt bì với những người ngoại theo Kitô giáo (Cvtd 15:1-21).

Trong thư Phaolô viết, Ngài nói đến việc gặp riêng với một vài nhân vật lãnh đạo quan trọng như Phêrô, Giacôbê, và Gioan. Và dù ba vị này đồng ý với Phaolô, nhiều người khác vẫn không đồng ý (Gal 2:1-10).

Với những Kitô hữu khác, sách Công Vụ Tông Đồ cho hay là Khanania phản đối Chúa khi được sai đón tiếp Phaolô: Lạy Chúa, con đã nghe lắm kẻ nói về người ấy, về tất cả những điều ác người ấy đã làm... (Cvtd 9:13-14).