The current video coding standard, High Efficiency Video Coding (HEVC), provides quad-tree structures of the coding unit (CU) to achieve high coding efficiency. Compared with previous standards, the HEVC encoder increases much computational complexity to levels inappropriate for applications of power-constrained devices. This work thus proposes a real-time complexity control scheme to control each frame complexity if the complexity of encoded frames is counted and its accumulated value is over the threshold. To further improve the coding efficiency, a fast CU depth decision algorithm is proposed. Experimental results show that a two-level of complexity control scheme was designed. In addition, the loss of the average BD-PSNR was about 0.23 dB and 0.27 dB as the target complexity was set to 80% and 60% of the unconstrained complexity, respectively.