Systems and methods are presented for efficient cross-fading of compressed domain information streams on a user/client device. Exemplary systems may provide cross-fade between AAC/Enhanced AAC Plus information streams, between MP3 information streams, or between information streams of unmatched formats. These systems are distinguished in that cross-fade is directly applied to compressed bitstreams so a single decode operation is performed on the resulting bitstream. Thus, a set of frames from each input stream associated with the time interval in which a cross fade is decoded, and combined and recoded with a cross fade or other effect now in the compressed bitstream. Once sent through the client device's decoder, the user hears the transitional effect. The only input data that is decoded and processed is that associated with the portion of each stream used the crossfade, blend or other interstitial, and thus the vast majority of input streams are left compressed.