By the time the album was released, the band's line-up had been their longest lasting so far, and the group had now been around longer since their 1989 reunion than they had when they originally existed in the late 1970s. For the release of "All Set", the band changed record labels to I.R.S. Records, as the band thought that the two labels they were signed to at the time, Castle Records (for UK distribution) and Caroline Records (for US distribution), were not far reaching enough. When asked about the change of label to I.R.S., Diggle explained that "we thought it would be a better move, you know, better distribution. Some people had problems finding "Trade Test"." "All Set" was released worldwide in May 1996 by I.R.S. Records, except in Japan where it was released by Real Cool Records instead on 21 June 1996. In the United Kingdom, it was released on 6 May as a CD and limited edition LP, whilst in the United States it was released on 14 May. The album title, "All Set", comes from an often repeated phrase from an American waitress.