In 1989 Frith was commissioned by choreographerBebe Miller to write a suite of music for the Brooklyn Academy of Music's "Next Wave" series. Frith composed and recorded the suite, Allies, in October 1989 with musicians Tom Cora and George Cartwright, with whom Frith had been collaborating for a number of years. The percussion on the recording was provided by a drum machine that Frith had programmed. Allies premiered at the Brooklyn Academy of Music in November 1989.
In August 1995 Frith began preparing Allies for release on an album, but was unhappy with the computerised drumming. He asked drummer Joey Baron of Naked City (in which Frith also played bass guitar) to re-record the drum tracks (six years after the original recording was made). The resulting mix was released by RecRec Music in 1996.