Innovations described herein facilitate the addition of temporal scalability to non-scalable bitstreams. For example, a bitstream rewriter receives units of encoded video data for a non-scalable bitstream from components of a hardware-based encoder. The bitstream rewriter changes at least some of the units of encoded video data so as to produce a scalable bitstream with temporal scalability. In doing so, the bitstream rewriter can associate an original sequence parameter set (SPS) and original picture parameter set (PPS) with pictures for a temporal base layer, and associate a new SPS and new PPS with pictures for a temporal enhancement layer. The bitstream rewriter can also alter syntax elements in the units of encoded video data, for example, changing syntax elements in a slice header in ways that avoid bit shifting operations for following coded slice data for a unit of encoded video data for the temporal enhancement layer.