H.264/AVC uses variable block size motion estimation (VBS-ME) to improve coding gain. However, its complexity is significant and fixed regardless of the required quality or of the scene characteristics. In this paper, we propose an adaptive complexity algorithm based on using the Walsh Hadamard Transform (WHT). VBS automatic partition and skip mode detection algorithms also are proposed. Experimental results show that 70% − 5% of the computation of H.264/AVC is required to achieve the same PSNR.