In this paper, a rate-distortion optimized variable block transform coding scheme is proposed based on a hierarchical structured transform for macroblock (MB) coding with a set of the order-4 and -8 integer cosine transform (ICT) kernels of H.264/AVC as well as a new order-16 ICT kernel. The set of order-4, -8 and -16 ICT kernels are applied for inter-predictive coding in square (4 × 4, 8 × 8 or 16 × 16) or non-square (16 × 8 or 8 × 16) transform for each MB in a hierarchical structured manner. The proposed hierarchical variable-sized block transform scheme using the order-16 ICT kernel achieves significant bitrate reduction up to 15%, compared to the High profile of H.264/AVC. Even if the number of candidates for the transform types increases, the encoding time can be reduced to average 4-6% over the H.264/AVC.