Video streaming applications over wireless networks present many challenges owing to the high packet error rate and the error characteristics of consecutive packets. In order to solve these problems, this paper proposes a cross-layer Unequal Error Protection (UEP) Forward Error Correction (FEC) mechanism with an interleaved strategy for video streaming over wireless networks. The proposed novel UEP mechanism uses a playable frame rate (PFR) model to determine the appropriate FEC redundancy for a varied type video frame. The UEP mechanism requires the video information to be obtained from the application layer in order to allocate FEC redundancy to each video frame in the Internet Protocol (IP) layer. Moreover, this paper aims to find out the appropriate length and depth of interleaving to overcome errors in consecutive packets. Our simulation results demonstrate that the proposed mechanism outperforms a related FEC mechanism with interleaving terms of playable frame rate.