The initial line-up was completed by the additionof young Swedish guitarist Yngwie Malmsteen, who had recently left Americanmetal band Steeler, and former Iron Butterfly drummer Jan Uvena, who had justrecently departed Alice Cooper's backing band. It was Shea that named the band"Alcatrazz"; the misspelling of the famous prison's name deliberate.

The band's debut album, 'No Parole from Rock 'n' Roll' wasreleased in late 1983 on Rocshire Records, MTV providing significant air timefor the video of lead single, 'Island in the Sun'. The album spent 18 weeks onthe Billboard charts and peaked at No. 128. A second video released in 1984 for'Hiroshima Mon Amour' also became popular in Japan where the band were awardeda gold record for their debut album.

Rocshire next released 'Live Sentence' in 1984; a concertrecording comprising tracks recorded during two shows at the Nakano Sun Plazain Tokyo on 28 January, 1984. This album peaked at No. 133 on the US Billboardcharts and a live video was also produced.

During this period, the band experienced increasing internaltensions between Malmsteen and Bonnet; the latter, according to Malmsteen,unhappy with the attention drawn to his guitar playing from fans rather than toBonnet's vocals. Matters came to a head with the two having an altercation onstage after Bonnet allegedly tampered with Malmsteen's amplifiers during aguitar solo at a show in Oklahoma. The resulting argument ended with Malmsteenassaulting Bonnet during the show, then leaving Alcatrazz to forge ahead withhis own band named Rising Force, which signed with Polydor Records. In fact,this merely hastened events as Waldo remembers Malmsteen having already decidedthat he would soon move on to form his own band.

Waldo replaced Malmsteen with former Frank Zappa guitaristSteve Vai, despite resistance from Bonnet, and the band signed with CapitolRecords after Rocshire shut down. New material was written and rehearsed withSteve Vai, before a headline tour of Japan was undertaken, which was againfilmed for a concert video.

Alcatrazz released its second album 'Disturbing the Peace' inthe spring of 1985, produced by Eddie Kramer who had worked with Led Zeppelin,Jimi Hendrix, and Triumph, among others. 'God Blessed Video' was the leadsingle and video, the album charting for 16 weeks. However, another line-upchange was in the wind as Steve Vai left to join David Lee Roth's solo band in1986. His departure was on excellent terms, as it was an offer that Vai couldnot refuse. He was replaced by guitarist Danny Johnson, who recorded whatbecame Alcatrazz's final studio album of the 1980s, 'Dangerous Games', releasedin September 1986. The album included covers of the Animals' song 'It's MyLife' and Marbles' song 'Only One Woman' (written by written by Barry, Robinand Maurice Gibb of the Bee Gees), Bonnet having been a member of Marbles in1968 when they released this song in the UK. Disheartened by the turnover inband members and a direction drifting into more commercial territory, Alcatrazzsplit up in 1987.

In 1998, the Renaissance Records label issued the compilationalbum 'The Best of Alcatrazz' and 'God Blessed Video' appeared in the 2002videogame soundtrack for 'Grand Theft Auto: Vice City', playing on fictionalrock station V-Rock. 

In the mid 2000's Bonnet formed a completely unsanctioned versionof the band as "Alcatrazz featuring Graham Bonnet" with musiciansunrelated to the original band.

Finally, in March 2017, three-fifths of the original line-up(Waldo, Shea and Bonnet) reunited for three shows in Japan, with ConradoPesinato and Mark Benquechea on guitar and drums respectively. The performanceswere recorded for the live album/DVD 'Parole Denied – Tokyo 2017', which wasreleased on 7 December, 2018. In February 2019 Alcatrazz was finally fullyresurrected with guitar virtuoso Joe Stump (formerly of Holy Hell and Reign ofTerror) joining to record a new album, which also included contributions fromChris Impellitteri, Bob Kulick, Dario Mollo and Steve Vai. Alcatrazz's firststudio album in 34 years, 'Born Innocent', was released on 31 July, 2020,through Silver Lining Music.

Not made public at the time in June 2020 a month before"Born Innocent" was released, Graham Bonnet quit Alcatrazz afterprivately declaring his dissatisfaction with playing heavy metal; ironically atype of music he feels no genuine affinity for. In his place, the bandrecruited ex-Rainbow vocalist Doogie White (also previously of Tank and MichaelSchenker's Temple of Rock). On 4 June, 2021, the first single from this newincarnation, 'Turn of the Wheel', was released. A second, 'Sword ofDeliverance', followed on 23 July before the album 'V' was released on 15October, 2021, again by Silver Lining Music. A harder-edged sound, the albumalso features guest contributions from drummer Nigel Glockler (Saxon), bassist DonnieVan Stavern (Riot), and a bass track from Cliff Evans (Tank). Around this time,personal issues forced Mark Benquechea to depart and drummer Larry Paterson(formerly of Chokehold and Blaze Bayley) joined the band as they made theirfirst UK tour in support of the album at the beginning of 2022.

Following a successful European tour, the quintet recordedthe band's sixth album 'Take No Prisoners' which will be released on 19 May2023 again through Silver Lining. The lead single 'Don't Get Mad Get Even',which features guest backing vocals from Girlschool and for which an animatedvideo was made, was released to coincide with a February UK tour.