Al joined Savatage in 1995, joining at the same time as Chris Caffery returned to the band; Caffery had previously been part of the band around the release of Gutter Ballet in 1989. Pitrelli played guitar on the albums Dead Winter Dead and (1995) The Wake of Magellan (1997), and performed some lead guitar work on Poets and Madmen (2001), despite being a member of Megadeth at the time. On that album, Pitrelli was responsible for the outro of "Stay with Me a While", the main solos of "Morphine Child" and "The Rumor", the first part of the main solo in "Commissar" and its outro. During his time with Savatage, he was asked by their producer Paul O'Neill if he was interested in joining his side project, the Trans-Siberian Orchestra. Pitrelli agreed and has played a role in all of their albums to date.
Pitrelli has been a core member of the group since their first album. As well as being the main lead guitarist, he is also the live musical director. TSO's 2007 tour program credits his "edgy playing and vast musical lexicon" with making him a perfect fit for the band's constant boundary-pushing progressive rock stylings. Pitrelli's leads are notable on "Tracers" and the instrumental "Toccatta – Carpimus Nocten", the latter being a piece co-wrote. Both songs form part of the group's fifth rock opera, on their 2009 album Night Castle.
Pitrelli was a member of Megadeth from 2000–02, replacing Marty Friedman. Megadeth bandleader Dave Mustaine asked him to join after hearing good reviews from their then-current drummer Jimmy Degrasso, with whom Pitrelli played during his days with Alice Cooper in the early 1990s. Pitrelli joined the band after an impromptu "audition" in front of a live crowd in Vancouver on January 16, 2000. Two nights after Friedman played his last show with Megadeth, Pitrelli was asked to play fifteen minutes before the show and was shocked by the prospect as they never rehearsed. He was present during the recording of Rude Awakening, a live CD/DVD that was released in 2002, and also performed on their 2001 album The World Needs a Hero. When Megadeth entered hiatus after Mustaine injured his arm, Pitrelli rejoined Savatage on April 9, 2002 and also continued his work with TSO.
More recently, Pitrelli has collaborated with Jane Mangini on a project entitled O'2L that has given both musicians critical acclaim. During the winter months, Pitrelli and Mangini have toured with Trans-Siberian Orchestra. In early 2010 they toured with TSO in the inaugural presentation of "Beethoven's Last Night".
In 1998, Pitrelli was featured on the video game album Sonic Adventure Remix, where he played guitar on a remix of the game's theme song "Open Your Heart".