Bostaph tok over som trommeslager i thrash metal-bandet Slayer da Dave Lombardo sluttet i 1992. Bostaph forlot gamlebandet, Forbidden, for å bli med i Slayer. I 1996 forlot han så Slayer for å fokusere på side-prosjektet Truth About Seafood, som han hadde startet mens han spilte i Forbidden. I 1997 returnerte han til Slayer, men forlot bandet igjen i 2001. Dave Lombardo kom så tilbake som trommeslager i Slayer. I 2005 ble Bostaph medlem av thrash metal-bandet Exodus, men forlot siden bandet i 2007 da originaltrommeslageren Tom Hunting ønsket å returnere til bandet. Paul Bostaph er for øyeblikket på utkikk etter et nytt band.
Paul Bostaph har turnerte også med Testament på deres gjenforenings-turné i 2006, men er ingen fast medlem av bandet.
I 2013 kom Bostaph tilbake til Slayer og i 2015 spilte han i albumet Repentless.