A method for decoding encoded data comprising integrated data and header protection is disclosed herein. In one embodiment, such a method includes receiving an extended data array. The extended data array includes a data array organized into rows and columns, headers appended to the rows of the data array, column ECC parity protecting the columns of the data array, and row ECC parity protecting the rows and headers combined. The method then decodes the extended data array. Among other operations, this decoding step includes checking the header associated with each row to determine whether the header is legal. If the header is legal, the method determines the contribution of the header to the corresponding row ECC parity. The method then reverses the contribution of the header to the corresponding row ECC parity. A corresponding apparatus (i.e., a tape drive configured to implement the above-described method) is also disclosed herein.