A coded bit stream converting apparatus comprises: syntax analyzing means (161) for inputting a first coded bit stream generated in a first coding scheme, and for extracting first header information in the first coding scheme and image coded data; decoding means (162) for decoding the first header information extracted; header information setting means (164) for setting and coding second header information in a second coding scheme in response to the first header information decoded by said decoding means; and multiplexing means (165) for generating a second coded bit stream by multiplexing image coded data extracted by said syntax analyzing means with the second header information coded by said header information setting means.