A method and apparatus for processing a multimedia bitstream are provided. The apparatus comprises a receive module, an extraction module, and a generation module. The receiving module receives the multimedia bitstream, wherein the multimedia bitstream comprises a plurality of NAL units. The extraction module extracts the NAL units from the multimedia bitstream. The generation module generates a processed bitstream comprising markers and NAL units. Each of the markers has a unique code. By doing so in future processing, a decoder or a decoding method can locate NAL units easily by searching for the corresponding marker.