Motion-compensated coding, which exploits the temporal redundancies in the moving images, is one of the most popular techniques currently used. Recently, a variable block size (VBS) motion estimation technique has been proposed to improve the performance of the motioncompensated transform coding (MCTC). This technique allows larger blocks to be used when smaller blocks provide little gain, saving the bit rates especially for areas containing more complex motion. However, there have been few efforts to investigate an efficient VBS motion structure for reducing the motion vector coding rates further. Hence, a new VBS motion estimation technique based on a hierarchical structure is proposed that improves the motion vector encoding efficiency and reduces the number of motion vectors to be transmitted as well. Specifically, the gain/cost motion estimation technique with the selective motion prediction is utilized for the topmost level motion vector search, exploiting the redundancies among the neighboring motion vectors. Also, a restricted search with respect to the topmost level motion vector enables more flexible and efficient motion vector encoding for the remaining lower level blocks. Intensive simulation on several moving image sequences show that the MCTC employing the VBS motion estimation provides a performance improvement of 0.7 to 1.0 dB, in terms of peak SNR, compared with the fixed block size motion estimation.