Techniques and tools for video coding/decoding with sub-block transform coding/decoding and re-oriented transforms are described. For example, a video encoder adaptively switches between 8×8, 8×4, and 4×8 DCTs when encoding 8×8 prediction residual blocks; a corresponding video decoder switches between 8×8, 8×4, and 4×8 inverse DCTs during decoding. The video encoder may determine the transform sizes as well as switching levels (e.g., frame, macroblock, or block) in a closed loop evaluation of the different transform sizes and switching levels. When a video encoder or decoder uses spatial extrapolation from pixel values in a causal neighborhood to predict pixel values of a block of pixels, the encoder/decoder can use a re-oriented transform to address non-stationarity of prediction residual values.