Phaolô sinh ra trong một gia đình Do Thái giáo (Rom 11:1; 2 Cor 11:22; Phil 3:5), và thuộc chi tộc Benjamin (Rom 11:1; Phil 3:5), chi tộc mang tên con út trong số 12 người con của Jacob. Tên Phaolô (tiếng Hi lạp là Paulos, tiếng La tinh là Paulus) còn có tên gọi là Saolô (tiếng Do Thái là Saul hay Sha   ul, Hi lạp là Saulos, và La tinh là Saulus).

Trong Cựu Ước, tục đổi tên của người Do Thái mang ý nghĩa quan trọng trong việc thay đổi đời sống, ơn gọi, nghề nghiệp, điạ vị xã hội v.v... Trường hợp tổ phụ Abram, từ này có nghĩa là "người cha của vinh dự" hay "người cha được vinh danh", sau khi được Thiên Chúa gọi thì được đổi tên là Abraham, nghĩa là "cha của số đông / cha của nhiều người" (Gen 17:5).

Tên Giacóp có nghĩa là "người nắm chân" vì Thánh Kinh kể ông sinh ra nắm chân người anh là Edau (Gen 25: 26). Sau khi vật lộn với thiên thần trong giấc mộng và được Thiên Chúa chúc phúc, ông được đổi tên là Israel, nghĩa là "người vật lộn với Thiên Chúa."

Trong những lá thư viết cho các giáo đoàn không hề thấy tên Saolô, và cũng không hề thấy Phaolô nhắc đến tên Saolô này. Cả hai tên Saolô và Phaolô được nhắc đến để chỉ cùng một người chỉ tìm thấy trong sách Công Vụ Tông Đồ mà thôi: "Saolô, còn được gọi là Phaolô" (Cvtd 13:9). Trước khi trở lại, Ngài được gọi là Saolô (Cvtd 7:58; 8:1-3; 9:1). Sau đó tên Phaolô được dùng thường xuyên.

Các học giả thánh kinh nghĩ rằng thánh Phaolô không đổi tên nhưng có hai tên cùng một lúc: tên Saolô được gọi trong gia đình và giữa những người Do thái; tên Phaolô được gọi trong gia đình và giữa những người Hi Lạp, vì Ngài lớn lên trong gia đình Do thái sống với người Hi Lạp. (Cũng như một người Việt Nam ở Mỹ có tên Michael khi đi học và Việt khi ở nhà hay ở với người Việt Nam).

Có hai lý do để tin việc này: thứ nhất, thánh nhân chỉ dùng tên Phaolô cho tất cả các thư và không hề nhắc đến tên Saolô; thứ hai là không thấy nói đến ý nghĩa của việc đổi tên như các trường hợp của các tổ phụ khác, dù tên Phaolô theo nghĩa gốc La tinh (Paulus) có nghĩa là "nhỏ bé."