Bostaph's first interest was to play bass but he decided to play drums because he found a drum kit cheaper than a bass guitar. He approached rock music listening to The Beatles and The Beach Boys, but AC/DC got him into rock drumming. He bought his first drum kit at 15 and, after listening to Killers by Iron Maiden, he wanted to become a metal drummer. Other influences include bands like ELO, Blue Öyster Cult and Black Sabbath. His biggest drumming inspirations are Phil Rudd, Clive Burr, Tommy Aldridge, Nicko McBrain, Cozy Powell, Jeff Porcaro, Steve Smith, Dave Lombardo, and Tommy Lee.
Bostaph attended Newark Memorial High School, in Newark, California. He had a strong dislike to his schooling years as he thought, "I felt I had enough to get me through every day life, why do I need more?" He was interested in sports and towards the end of his first year, his interest in music began, and he got a job, which took priority over his schooling.
Bostaph played drums for Forbidden from 1985–1992, playing on their first two studio albums, Forbidden Evil and Twisted into Form. He also played on their 1989 live EP Raw Evil: Live at the Dynamo. He is regarded as their most prolific 'permanent' drummer to date. Bostaph had joined the band First Strike.
Following the departure of Slayer drummer Dave Lombardo in 1992, the band was looking for a new drummer. Lombardo's drum tech was filling in but constantly made errors. After auditioning several drummers and listening to hundreds of demo tapes, Bostaph was recommended by Slayer guitarist Kerry King's guitar technician. Slayer members listened to Forbidden records, however, they did not see how Bostaph could fit into the Slayer momentum – Lombardo's style being "over the top", while Forbidden was more melodic. Slayer auditioned Bostaph with nine songs, and he made only one error on "Angel of Death". Bostaph had to continually practice to improve the strength of his hands and feet; "I respected and loved Dave's drumming but as a fan, if they got a new drummer and I bought a ticket to a show, I would expect to hear the stuff that Dave does, that's what I would want. So, I went in and every time I had to learn a new song I would play them exactly how Dave played them".
Bostaph recorded four albums with Slayer; his least favorite is 1994's Divine Intervention. This is due to the guitars not being loud enough as they were in the recording session, moving around to several recording studios, and a producer who had never done any heavy metal music. The producer changed near the end of recording to Toby Wright – Bostaph stating "that record never had any consistency to it although a lot of fans still like it." Bostaph left the band in 1996 to concentrate on his solo project, Truth About Seafood, and was replaced by Jon Dette; however, he returned in 1997. His second favorite album is 2001's God Hates Us All; "The whole era that I was with the band that was the album that was the most well-rounded and mixed the best" with Diabolus in Musica.
Bostaph departed from Slayer after the release of God Hates Us All, following a chronic elbow injury he had sustained that would hinder his ability to play. (although he later revealed that the actual reason for departure is because "Musically, I wanted to do something else".) His third last performance with the band is recorded on the DVD War at the Warfield recorded on December 7, 2001. Bostaph is yet to watch it as he feels "It's like breaking up with a girlfriend" and needs to move on with his life. He remained friends with Slayer members, and when asked if he would work with them in the future, he replied "sure". Bostaph was temporarily replaced by original Slayer drummer Dave Lombardo, which later proved to be a permanent arrangement until 2013, when the band announced he has replaced Lombardo for the second time.
Unwilling to give up music, Bostaph joined Systematic in 2003 – a band which he had previously formed with vocalist Tim Narducci and guitarist Adam Ruppel before recording Slayer's Diabolus in Musica. Bostaph introduced the band to Slayer's manager – Rick Sales – to help the band gain notice. As the band needed a drummer in 2003, Bostaph was willing to help out.
Bostaph toured with Systematic for four months, although departed in 2004 stating: "I wasn’t having very much fun and it’s not for me." In 2003 Bostaph sustained an injury to his knee, while playing soccer. After finishing Systematics tour, Bostaph underwent surgery – not touching a drum kit for over a year until he received a phone call from Exodus members.
Bostaph received a phone call from Exodus' manager, who asked him to join the band. Exodus bass guitarist Jack Gibson talked to guitarist Gary Holt if they should recruit Bostaph – Holt knew Bostaph while Exodus toured with Forbidden, as both bands were from the San Francisco Bay Area. When Bostaph received the phone call, two members had already left Exodus, and drummer Tom Hunting was thinking about leaving. Bostaph knew how to play all the records except for Impact Is Imminent, and recorded drums on the band's 2005 album Shovel Headed Kill Machine.
Bostaph asserts the album is different from the band's previous albums; "It's so different because Bonded... was such a landmark record, such a great record that…I watched the band the whole time and I think this is a more, probably, the most brutal record the band has done since Bonded by Blood." Bostaph also says the chemistry between members was very different, due to three out of five members being replaced in one year; "it's a totally different band than before." The band toured for over a year promoting Shovel Headed Kill Machine, and wished to enter the recording studio to record another as soon as possible. However, on March 28, 2007, Bostaph announced that he parted ways with Exodus; "They now have their original drummer Tom Hunting back in the band. I always said from the start if Tom ever wanted to come back, the drum throne is his. I have the greatest respect for Tom and his playing." Bostaph also announced he is no longer endorsing TAMA drum kits, and is proud to represent Drum Workshop and their products.
Testament's official website announced Bostaph rejoined the group in October 2007. The Formation of Damnation was the first Testament studio album of all new material in nine years, and the first to feature Alex Skolnick on guitar since 1992's The Ritual, also the first to feature bassist Greg Christian since 1994's Low was released on April 29, 2008. This is also the first full length Testament studio album to feature Paul Bostaph on drums. This album was awarded the 2008 'Album of the Year' by the Metal Hammer Awards.
In June 2011, Testament began recording their next studio album, entitled Dark Roots of Earth, expected to be released on April 27, 2012. However, due to a "serious injury", Paul was not involved in the recording sessions; Gene Hoglan (who previously played on the band's 1997 album Demonic) filled in for him. He was expected to rejoin Testament when they tour to support the album. However, frontman Chuck Billy stated in December 2011 that Bostaph has left the band again.
Bostaph is also a member of a tribute band called HAIL!. HAIL!'s rotating cast of members include Andreas Kisser, Tim "Ripper" Owens, David Ellefson, Mike Portnoy, Jimmy DeGrasso and Roy Mayorga. Ripper, DeGrasso, Ellefson and Kisser formed the band in late 2008. The band, toured Europe in 2009 and in June 2010 HAIL! is on their second European tour with the following line-up: Andreas Kisser, Tim "Ripper" Owens, Paul Bostaph and James LoMenzo. Due to the death of announced bassist Paul Gray, LoMenzo agreed on only one day's notice to fly to Portugal and rescue the Rock in Rio Festival where HAIL! was scheduled to perform on May 30, 2010.
On May 30, 2013, Slayer announced via their official Facebook page that Paul Bostaph had returned once again to replace long-time member Dave Lombardo behind the kit on a full-time basis. He is featured on Slayer's eleventh studio album Repentless.