Prvi dodir s matematikom duguje svojim roditeljima koji su oboje bili profesori matematike u srednjoj školi. Nakon gubitka dvije kćeri majka se prema Paulu postavila veoma zaštitnički i školovala ga je kod kuće. U nedostatku vršnjačkog društva Paul se okrenuo udžbenicima i zbirkama zadataka iz matematike te se zabavljao rješavanjem problema. Kako je sam rekao - “oni [brojevi] su mi bili prijatelji.”

Sa 17 godina krenuo je na fakultet na Sveučilištu Pázmány Péter u Budimpešti gdje je u samo 4 godine završio studij i stekao doktorat iz matematike. Od svih brojeva, najdraži su mu bili prosti brojevi (prirodni brojevi veći od 1 koji su djeljivi samo s 1 i sa samim sobom). Već se tijekom studija istaknuo dokazavši Bertrandov postulat koji kaže da uvijek postoji prosti broj između bilo kojeg prirodnog broja i njegove dvostruke vrijednosti.

Zbog porasta antisemitizma u Mađarskoj 1934. godine odlazi u Englesku, a nedugo potom seli u SAD gdje prihvaća poziciju na Institutu za napredna istraživanja u Princetonu. Nakon godinu dana rada na institutu započinje pola stoljeća njegova “nomadskog života” koji ga je učinio živućom legendom. Putovao je po raznim američkim, ali i ostalim svjetskim sveučilištima rješavajući koji god mu je matematički problem bio predstavljen pod motom “još jedan krov, još jedan dokaz - Another roof, another proof.”

Legenda kaže da se nepozvan pojavljivao na vratima kolega s aktovkom u ruci u kojoj je, uz bilješke, bilo par komada odjeće, i svečano se najavljivao riječima: “Moj um je otvoren.” „U gostima“ bi ostajao sve dok problem nije bio riješen, a gostoprimstvo domaćina bilo bi nagrađeno koautorstvom rada s jednim od najvećih matematičkih umova dvadesetog stoljeća. Putovao je u preko 20 zemalja što ga je u vrijeme Hladnog rata učinilo sumnjivom ličnošću, kako za Amerikance, tako i za sovjete.

Matematiku je proučavao tolikim žarom da je radio i po 19 sati dnevno uz pomoć ogromnih količina kave i amfetamina. Za života je objavio oko 1500 znanstvenih radova s 507 različitih koautora, od kojih najviše iz područja kombinatorike, teorije grafova i teorije brojeva. Tako je u matematičkoj zajednici nastao „Erdősov broj“ – mjera udaljenosti autorstva od Erdősa. Primjerice, onima koji su objavili rad s Erdősom dodijeljen je broj 1, onima koji su objavili rad s jednim od njegovih koautora dodijeljen je broj 2, a onima koji su surađivali s koautorom koautora dodijeljen je broj 3 i tako dalje.

Zanimljivo je da je i sam Erdősov broj postao predmetom istraživanja u studijama uzoraka u koautorstvu znanstvenih publikacija. Radio je sve do smrti protivivši se ideji da je matematika rezervirana samo za mlade umove. Preminuo je od srčanog udara u 83. godini života, samo nekoliko sati nakon što je predao rad za matematičku konferenciju.