A Maximum Likelihood Sequence Estimation (MLSE) decoder that decodes an encoded sequence of data symbols includes a branch metric unit for computing branch metrics for each trellis stage of the encoded sequence, a path metric unit for computing a path metric for each trellis stage using the computed branch metrics, and an M-at-a-time traceback unit for performing an M-at-a-time traceback operation using the computed path metrics. The M-at-a-time traceback operation generates M decoded data symbols in a single M-at-a-time traceback operation.