Methods, apparatus, and articles of manufacture for performing data insertion in compressed audio/video data streams are disclosed. Example methods disclosed herein include receiving an input multi-program data stream including a first compressed media data stream associated with a media program and a second data stream containing descriptive information describing the media program, rearranging data in frames of the first compressed media data stream to form contiguous sequences of skip bytes at respective locations in the frames of the first compressed media data stream, extracting the descriptive information from the second data stream, inserting payload data prepared from the descriptive information at the locations of the contiguous sequences of skip bytes in the frames of the compressed media data stream, and recombining the second data stream with the compressed media stream after inserting the payload data to form an output multi-program data stream.