Disclosed are various embodiments directed to transcoding a bit stream in parallel. A bit stream may be divided into a plurality of segments, where a plurality of transcoders encode at least a portion of the segments in parallel. If encoding is performed using variable bit rate (BR) encoding, each encoder may encode a segment and vary a BR for the segment. A measured average BR is compared with a target average BR to determine whether to adjust a video quality level (VQL) or any other encoder parameter. A relatively constant subjective quality may be maintained using variable BR encoding while achieving a target average BR. When using constant BR encoding, a VQL or other encoder parameter is used by encoders to achieve relatively constant subjective quality. For example, a relatively continuous quantization parameter between adjacent encoded segments may be achieved.