Recent development of portable devices and prevalence of high-throughput communication infrastructures make the video encoding in portable devices on high demand. However, its computational complexity makes the implementation of real-time video encoder on portable devices extremely difficult. Many fast algorithms to solve the problems are not efficient from the view point of worst workload since they consider only reduction of average computational complexity. Moreover, since the amount of reduction of computational complexity highly depends on video sequence, fixed fast algorithms cannot always achieve their full potential for real-time encoding. In this paper, we analyze the complexity of H.264/AVC video coding tools, and develop two parameters for complexity control. Consequently, we design a power-aware complexity scalable encoding scheme implementable on embedded system. Using our target embedded system, the proposed method is verified to save power by about 50%.