Techniques and tools for sub-block transform coding 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. The encoder and decoder may use different scan patterns for different transform sizes when scanning values from two-dimensional blocks into one-dimensional arrays, or vice versa. The encoder and decoder may use sub-block pattern codes to indicate the presence or absence of information for the sub-blocks of particular blocks.