One of the new features adopted in H.264/AVC is the utilization of flexible block size ranging from 16x16 to 4x4 in inter-frame coding. The aim is to reduce the error due to fixed block size prediction within a macroblock. However, this feature requires extremely computational complexity. In this paper, we proposed a residual texture based fast block size selection algorithm for inter-frame coding. Firstly, we perform a motion estimation (ME) for a macroblock and get the residual; then we predict the block size by analyzing the residual texture. Extensive simulations verify that the proposed method speeds up the block-size selection procedure by 50% without sacrificing picture quality and compression ratio.