Selecting an efficient variable block size mode in H.264 video coding standard for better compression performance is considered. The proposed scheme is based on a 3D recursive search algorithm and takes into account the motion vector cost and previous frame information. The best mode for the current macroblock is obtained by analysing the modes for a maximum of four macroblocks in the current and previous frames. An improvement in the encoding time with negligible impact on subjective and quantitative performance has been achieved.