Matematikatanár szülei, Erdős Lajos és Wilhelm Anna igen korán felfedezték tehetségét. Négyéves korában magától, spekulatív úton rájött a negatív számok létének szükségszerűségére. Gausshoz hasonlóan tehát csodagyerekként indult, a Szent István Gimnáziumba járt, és a Középiskolai Matematikai és Fizikai Lapok feladatmegoldó versenyeinek állandó résztvevőjeként akadálytalanul jutott a Pázmány Péter Tudományegyetem matematika-fizika szakára, ahol Fejér Lipót volt rá a legnagyobb hatással. Mivel itt sem sikerült a matematikai problémák iránti "született nyughatatlanságát" csillapítania, a Műegyetemre is áthallgatott.
Már egyetemi diákként szakmai műhelyeket szervezett. Folyton újabb és újabb problémákat vetett fel a legkülönfélébb matematikai területekről - különösen a számelmélet, halmazok és gráfok, valamint az analízis izgatta -, és ezzel szinte kiprovokálta diáktársai problémamegoldó kedvét. Ezt később úgy módosította, hogy kérdéseinek jó megoldását a feladat nehézségével arányos pénzjutalommal honorálta. Jellemző, hogy egyik, még egyetemista korában, Turán Pállal közösen felvetett sejtését szűk fél évszázad múltán oldotta meg Szemerédi Endre (vele készült interjúnk: "Mostanában már pironkodva elismerik", Magyar Narancs, 2012. április 5.), aki ezzel nemcsak a felajánlott ezer dollárt, de az MTA levelező tagságát is elnyerte.
Erdős 1934-ben végzett az egyetemen, Fejér Lipótnál doktorált, majd négy évre szóló ösztöndíjjal Manchesterbe utazott. Időnként hazalátogatott, de 1938-ban úgy érezte, Magyarország immár nem élhető hely a számára, és az Egyesült Államokban telepedett le. A politikától tudatosan távol tartotta magát, magyar állampolgárságát megtartva igazi világpolgárként mindig úton volt, s minden percét a tudományra fordította. 1956-ban a Magyar Tudományos Akadémia levelező, 1962-ben rendes tagja lett. Ettől kezdve rendszeresen járt haza, felkarolta a tehetséggondozás ügyét, inspirálta a később világhírűvé vált magyar kombinatorikai és halmazelméleti iskola megszületését. Az MTA-n kívül tagja volt az amerikai, a holland, az ausztrál és az indiai akadémiának, valamint a Royal Societynek is. 1983-ban megkapta a legrangosabb matematikai kitüntetést, a Wolf-díjat.
Tudományos munkásságát tekintve igen termékeny volt. A 30-as években Mark Kaccal és Aurel Wintnerrel a valószínűségi számelmélet születésénél bábáskodott, egykori diáktársával, Turán Pállal az approximációelmélet és a statisztikus csoportelmélet terén hozott máig időtálló eredményeket. Ő alkotta meg a halmazelméletben ismert partíciókalkulust, az ugyancsak színes egyéniségnek számító Rényi Alfréddal pedig kidolgozta a véletlen gráfok elméletét. Problémamegoldó munkásságának kiemelkedő epizódja az Atle Selberggel 1949-ben közösen publikált elemi bizonyítás a prímszámtételre. A kombinatorikában ismert átlós Ramsey-számokra máig időtálló becslést adott, az alsó és felső értékeket azóta sem sikerült nála sokkal pontosabban meghatározni. Az egyszerű, "szép" megoldások híve volt, bármilyen nehéz problémáról is volt szó.
Matematikai lapokban közölt publikációinak száma elérte a másfél ezret, s további ötszáznak volt társszerzője. Ez utóbbira alkalmazta azt a félig tréfás, félig komolyan vett faktort, amit azóta csak "Erdős-szám" néven használnak. Ennek lényege, hogy 1-es számot kapott, akinek vele közös szakcikke jelent meg, a velük ugyanilyen kapcsolatban állók 2-est kaptak, és így tovább. Egyik magyar tanítványa, az 1-es Erdős-számmal rendelkező Tuza Zsolt szerint az értékmérő módszert nem Erdős találta ki, de igen megtetszett neki. A "számozást" később más tudományágak művelői is átvették, sőt az informatika a hálózati viszonyok leírásában alkalmazza az elemek közti távolság leképezésére.
Noha Erdős tisztában volt a számítógépes adatfeldolgozás fontosságával, ő maga nem tért el az "ősi módszertől": számításait, képleteit saját kezűleg vetette papírra. Így is korszakos matematikusként tekintett rá a tudományos világ, vannak, akik "korunk Eulerje"-ként emlegetik.
Családot nem alapított, az általa létrehozott ironikus "Erdős-szótár" meghatározásával élve nem lett "rab" (férj), és az "epszilon" (gyermek) gondja sem nyomasztotta. Egy 1984-es tévéinterjúban azt mondta: "Rövid ideig él az ember, és sokáig halott." Ő azokat nevezte "halottnak", akik nem érdeklődtek a matematika iránt, vagy elfordultak tőle.
Erdős Pál egész életét a matematika töltötte ki. 1996-ban, egy varsói szállodában hunyt el szívroham következtében. 83 évesen, útközben.
