For entropy-coded H.263 video frames, a transmission error in a codeword will not only affect the underlying codeword but also may affect subsequent codewords, resulting in a great degradation of the received video frames. In this study, a new error resilient coding scheme for H.263 video transmission is proposed. At the encoder, for an I frame, the important data of each macroblock are extracted and embedded into another macroblock within the I frame by the proposed odd-even data embedding scheme for I frames. For a P frame, a rate-distortion optimized coding mode selection approach is employed. The important data for each GOB (group of blocks) are extracted and embedded into the next frame by using the proposed macroblock-interleaving GOB-based data embedding scheme. At the decoder, after all the corrupted macroblocks within a video frame are detected and located, if the important data of a corrupted macroblock can be extracted correctly, the extracted important data will facilitate the employed error concealment scheme to conceal the corrupted macroblock; otherwise, the employed error concealment scheme is simply used to conceal the corrupted macroblock. Based on the simulation results, the proposed scheme can recover high-quality H.263 video frames from the corresponding corrupted video frames up to video packet loss rate = 30%.