Gilbert soitti nuoruudessaan lukuisissa yhtyeissä. Hänet löysi Shrapnel-levy-yhtiön kykyjenetsijä Mike Varney, joka auttoi silloin 15-vuotiasta Gilbertiä kehittymään muusikkona. Vuonna 1985 Varney löysi Gilbertille yhtyeen. Näin muodostettu Racer X julkaisi kolme studioalbumia, minkä jälkeen Gilbert erosi yhtyeestä vuonna 1988.[1] Hän myös kokosi sen jälleen yhteen vuonna 1999. Gilbert soittaa myös Beatles-covereita soittavassa Yellow Matter Custard -kokoonpanossa, jossa soittaa muun muassa Dream Theaterin entinen rumpali Mike Portnoy.
Yhdessä basisti Billy Sheehanin kanssa Gilbert perusti vuonna 1989 Mr. Bigin. Gilbert on mukana yhtyeen viidellä studio- ja viidellä livealbumilla. Hän jätti yhtyeen vuonna 1996 keskittyäkseen soolouraansa.
Gilbert on yhteistyössä kitaravalmistaja Ibanezin kanssa, ja käyttää IbanezinPaul Gilbert Signature -sarjan PGM-kitaroita ja vaihtelevia Ibanezin muita malleja. Paul Gilbert käytti 80-luvulla kelluvilla "Edge"- ja "Kahler"-talloilla varustettuja kitaroita.