Roman citizenship was immensely important in the NT era, and Paul was able to claim it—and more; he was also a citizen of Tarsus. His Roman entitlement probably derived from his father and grandfather and it provided exemption from degrading punishments. Citizenship of Tarsus conferred merely local privileges. How the tribune at Jerusalem could ascertain that Paul was speaking the truth in making his claim to be a Roman citizen, according to the account in Acts 22: 27–9, is uncertain. But birth certificates, being copies of official records, have been discovered in Egypt and perhaps a record was kept at Rome.
One suggestion about how Paul's family secured Roman citizenship is that they were once Jewish slaves taken by Pompey in 63 BCE and deported to Tarsus, and there freed and honoured.