A high-quality, low-complexity audio time scale modification (TSM) algorithm useful in speeding up or slowing down the playback of an encoded audio signal without changing the pitch or timbre of the audio signal. The TSM algorithm uses a modified synchronized overlap-add (SOLA) algorithm that maintains a roughly constant computational complexity regardless of the TSM speed factor and that performs most of the required SOLA computation using decimated signals, thereby reducing computational complexity by approximately two orders of magnitude.