I asked this question to Keith Rabois (ex-PayPal) once and he said it best "it's because we were started in a downturn economy, and it allowed us to hire great people who otherwise would've been starting their own company, so that meant we had the highest IQ per sq/ft than any other company in the valley".
So I think it's great timing, idea, initial team and luck.
Keep in mind PayPal began without an idea of becoming the PayPal we all know and use today. They initially started with the idea of greatness to find an area of the market they could serve but in my opinion they went too broad - which led to the disagreement of Elon Musk and their then CEO. Musk decided to refocus the vision of the company on providing one great product rather than multiple. Through his vision, he assembled a team keeping them focused on their individual tasks to be performed with excellence, while he maintained his responsibility was ensuring they steered the course of PayPal toward its innovative vision. This is a great example of leadership exuded by some of the most winningest CEO's and Leaders in history.