An apparatus and method for determining interleaved addresses of a turbo interleaver are disclosed. A new interleaving size of received data is compared with a previously-stored interleaving size. When the compared interleaving sizes are equal to each other, the received data is decoded using previously-stored interleaved addresses. When the compared interleaving sizes are different from each other, the received data is decoded using new interleaved addresses generated with the new interleaving size. The turbo interleaver generates interleaved addresses at minimum number of code blocks rather than every code block, resulting in reduction of decoding delay and improvement of decoding performance.