Innovations in video playback using a browser-based video decoder are described. In a computer system that includes multiple central processing units (“CPUs”), a browser-based video decoder performs operations with multiple threads that may execute simultaneously on different CPUs. The video decoder can perform decoding operations in parallel for different sections of a picture. For example, with a main CPU thread associated with a browser, the video decoder performs a first decoding workload (e.g., bitstream parsing) for a picture. With auxiliary CPU threads associated with Web workers and simultaneously executing on different CPUs, the video decoder performs a second decoding workload (e.g., entropy decoding, decoding of side information) for different sections of the picture, one section per auxiliary CPU thread. If the computer system also includes a graphics processing unit (“GPU”), the video decoder can perform additional decoding workloads with shader routines executable on the GPU.