A joint rate-distortion-complexity H.264 motion search framework is proposed to balance the encoder's coding efficiency and complexity in an embedded system environment. Under our framework, the complexity of H.264 motion search is primarily measured by the execution time of the sum of absolute differences (SAD) calculation. Two Lagrange parameters are used to terminate the complexityinefficient motion search rounds and skip redundant motion search of small block modes, respectively. Then, the relationship between the weighted complexity and the Lagrange parameters is explored to allocate the complexity cost among different coding units. It is demonstrated by experimental results that the proposed method can reduce the complexity without much sacrifice in coding efficiency.