Network impairments such as delay and packet losses have severe impact on the presentation quality of many predictive video sources. Prior researches (e.g., [1]-[3][5]-[9][11]-[13]) have shown efforts to develop packet loss resilient coding methods to overcome such impairments for realtime streaming applications. Interleaved Source Coding (ISC) is one of the error resilient coding methods, which is based on an optimum interleaving of predictive video coded frames transmitted over a single erasure channel. ISC employs a Markov Decision Process (MDP) and a corresponding dynamic programming algorithm to identify the optimal interleaving pattern for a given channel model and a transmitting sequence. ISC has shown to significantly improve the overall quality of predictive video coded stream over a lossy channel without complex modifications to standard video coders [7][8]. In this paper, ISC is evaluated over channels with memory. In particular, we analyze the impact of packet correlation [15][16] of the popular Gilbert model on ISC-based packet video over a wide range of packet loss probabilities. Simulations have shown that ISC advances the traditional method as either the loss rate increases or the packet correlation decreases.