A method and apparatus for transmitting a streaming media with Forward Error Correction (FEC). Upon receiving the streaming media, the technique includes: encoding, segmenting and packeting frames comprised therein to generate a packetized elementary stream of media packets with variable sizes; for each L sequential media packets, calculating a “random loss” (RL) FEC parity and generating a respective RL FEC packet associated therewith; calculating “burst loss” (BL) FEC parities in accordance with a predefined FEC scheme and generating respective BL FEC structures bearing FEC headers and usable for generating BL FEC packets; calculating size-related parameters of a group of sequential media packets, the group being selected in accordance with the FEC scheme; and, transmitting the packetized elementary stream with interleaved FEC packets. The BL FEC packets are transmitted merely when the calculated size-related parameters meet a size-related burst loss (SRB) criterion defined by the FEC scheme.