With the rapid improvement in computer and network technologies high-bandwidth streaming multimedia applications are now possible on the Internet. However, the Internet does not provide the necessary Quality of Service (QoS) guarantees needed to support high-quality, real-time multimedia Transmission, causing Internet multimedia applications to suffer from delay, jitter and loss. Among these, loss, typically caused by network congestion, can degrade the perceptual quality of multimedia streams the most. We propose a video interleaving approach that ameliorates the effects of frame loss by spreading out the bursty effects of loss. The sender first resequences data before transmission to help distribute loss, and returns the data to their original order at the receiver. We apply our approach to MPEG and evaluate the benefits of interleaving to perceptual quality with user studies. Our results show that interleaving adds a small amount of delay and bandwidth overhead, while significantly improving the perceptual quality of Internet video.