Paul of Tarsus is assumed to have existed. The only evidence for him is his works in the Bible - seven written by the same author, a few more by this author with others' text mixed in, a few clearly not written by this author - but this is evidence that one person, who called himself Paul, wrote these things. I suppose it's possible he was an entirely fictional construct, but scholars tend to go with "dude wrote this stuff." Much like Socrates (and unlike Jesus), his existence is secondary to his body of work.