Aspects of a method and system for decoding GSM speech data using redundancy are provided. A decoding algorithm in a frame process may be utilized to generate a bit-sequence for GSM speech data received via a burst process. The decoding algorithm may be a modified Viterbi algorithm, for example. The frame process may comprise verifying a CRC for the bit-sequence and/or decrypting the bit-sequence. In some instances, estimates of the bit-sequence may be fed back to the decoding algorithm. A speech stream that satisfies speech constraints may be generated based on the generated bit-sequence. The speech constraints may comprise gain and/or pitch continuity, for example. The generated speech stream may be decoded via a voice decoder that supports full rate (FR), adaptive multi-rate (AMR), and/or enhanced full-rate (EFR) speech coding. Frame process results may be fed back to the burst process to improve decoding of received GSM speech data.