Rođen je u Dablinu, kao najmlađi od sedmoro dece. Diplomirao je na La Chambre Syndicale de la Haute Couture u Parizu.

Danas ima ležeran odnos prema formalnom obrazovanju i kaže da je najviše naučio zahvaljujući tome što je živeo u Parizu u vreme Ungaroa i Cardina. Dodatno se usavršavao u Milanu, a početkom devedesetih je njegov brend bio toliko snažan da se mogao pohvaliti spektakularnom prodavnicom u Najtbridžu i velikim interesovanjem u Skandinaviji i Americi.

Costelloe je sinonim za praktičnost i osvežavajuću nepretencioznost, pa je tako izuzetno ponosan na činjenicu da je dizajnirao uniforme za Aer Lingus i British Airways. Međutim, njegove modele nosile su i princeza Dijana i grofica Sofija od Veseksa.

Paul Costelloe kaže da dizajnira za “prave” žene. “Postoji ogroman jaz između onog što izgleda sjajno na manekenki koja je mršava kao grisina i onog što izgleda sjajno na pravoj ženi”, kaže Costelloe.  Tvrdi da, kao i Coco Chanel, više voli stil nego modu: “Neke etikete pripadaju visokoj modi i u tome ima izvesne sigurnosti, ali su rizične nemate osamnaest ili dvadeset i osam godina. Međutim, Armani i Costelloe su etikete koje možete nositi i u sedamdesetoj godini.”