The album was released in memory of Randy Rhoads, guitarist for Osbourne's band between 1979 and 1982 who died in a plane crash while on tour in Florida in 1982. The album also includes studio outtakes of Rhoads recording the classical-influenced acoustic guitar piece "Dee", which Rhoads wrote for his mother Delores and which was originally included on Osbourne's debut solo album Blizzard of Ozz.
A live album consisting entirely of renditions of Black Sabbath songs was originally planned to be recorded at Toronto's Maple Leaf Gardens in mid-1982 with Rhoads. Rhoads and drummer Tommy Aldridge felt that they had established themselves as recording artists and an album of cover songs would be a step backwards artistically, and they refused to participate. Bassist Rudy Sarzo was uncomfortable with refusing to perform, not having the same recording pedigree of his bandmates, but he stood with them and the trio informed management of their decision. Osbourne felt betrayed and his relationship with Rhoads never fully recovered. Plans for this proposed live album crumbled upon Rhoads' sudden death weeks later, though the plan was resurrected with the release of Speak of the Devil later that year with future Night Ranger guitarist Brad Gillis.
The majority of Tribute, from "I Don't Know" through to "Paranoid", was recorded live in Cleveland, Ohio on 11 May 1981, with the exception of an extended guitar solo midway through the song "Suicide Solution" which was recorded at Théâtre Saint-Denis in Montreal on 28 July 1981 and inserted into the song. Osbourne stated upon the album's release in 1987 that the entire album had been recorded "somewhere in Canada", though he may have been confusing it with that Montreal recording from which the guitar solo was taken. This particular Montreal show had been recorded and released in 1981 for a radio program called the King Biscuit Flower Hour, which may account for Osbourne's confusion. "Goodbye to Romance" and "No Bone Movies" are taken from an earlier English gig in support of the Blizzard of Ozz album, possibly from Southampton on 2 October 1980. These two tracks feature bassist Bob Daisley and drummer Lee Kerslake.
The recording of "Crazy Train" that appears on this album was also released as the album's only single on 10 February 1987, along with an accompanying music video. The album's cover photo was taken at a performance in Rosemont, Illinois on 24 January 1982, by photographer Paul Natkin.
The operatic music which opens Tribute, as well as all of Osbourne's live shows of that era, is "O Fortuna" from the Carmina Burana scenic cantata by Carl Orff. This introductory music was omitted from the 1995 remaster, with opening track "I Don't Know" subsequently being shortened to 4:43.