New Order had been on hiatus as of late 1993 following the turbulent recording and touring of the successful Republic album. The individual members had returned to the side projects that had occupied them during the group's previous hiatus that lasted 1989 to 1992. Republic had been the first album that the group had released for London Records, and with the group announcing little intention of working together the label went ahead compiling The Best of New Order. This venture had proven popular, and sold very well in the competitive Christmas market. It neatly collected most of the band's hits into one package. The hits album was promoted by two singles, remixes of "True Faith" and "1963"; these too proved to be popular. Clearly there was still a market for New Order.
The compilation was released on Compact Disc, cassette and double LP. Each version has a different track listing. Cassette editions include an additional mix of "Temptation", while limited editions of the CD and cassette came with an additional bonus disc/cassette of "Blue Monday" remixes. This version replaces the white background on the cover with a reflective brown/gold. The album reached #5 on the UK Albums Chart as well as #41 on the Swedish albums chart. To promote the album, "Blue Monday" was once again re-released. The single was backed with remixes that appear on the bonus disc of the limited edition CD. The version of "Blue Monday" released was the Hardfloor Mix, dubbed "Blue Monday-95", and reached #17 in the UK, No. 54 in Germany, and #29 in Ireland.
At the time of the release, the compact disc version was amongst the longest compact discs released, clocking in at 80:02 with the pregap included. Without the pregap, the compact disc would clock in at 80:00, seconds longer than the recognized official compact disc duration limit.
The unusual figure on the cover is a pink version of the blue stylised question mark featured on the cover of The Best of New Order. Sometimes in chart books, this album is listed as ? (The Rest of) New Order.