A computer-implemented system and method are described for performing video compression. For example, a method according to one embodiment comprises: encoding a plurality of video frames or portions thereof according to a first encoding format; transmitting the plurality of encoded video frames or portions to a client device; receiving feedback information from the client device, the feedback information usable to determine whether data contained in the video frames or portions has not been successfully received and/or decoded; in response to detecting that one or more video frames or portions thereof have not been successfully received and/or decoded, then either encoding a new video frame or portion thereof according to a second encoding format or encoding the new video frame to be dependent on the last video frame or portion thereof known to have been successfully received and/or decoded, and: (1) if no forward error correction (FEC) coding is used to transmit the plurality of encoded video frames or portions, then encoding a new video frame or portion thereof using FEC coding; or (2) if a first FEC coding is used to transmit the plurality of encoded video frames or portions, then encoding a new video frame or portion thereof using a second FEC coding, the second FEC coding being a relatively stronger FEC coding than the first FEC coding; and transmitting the new video frame or portion thereof to the client device.