A complexity-constrained inter-mode decision algorithm for H.264/AVC video coding is developed using a rate-distortioncomplexity (RDC) optimization framework in this work. The proposed algorithm consists of two main steps. At the first step, we use the number of DCT coefficients of prediction errors quantized to zeros to predict whether the underlying block modes should be skipped. At the second step, a joint RDC cost function is adopted to control the mode decision process to manage motion search complexity. It is demonstrated by computer simulation that significant complexity saving can be achieved with negligible R-D performance degradation.