This paper proposes a new complexity model for H.264/AVC video decoding. The model is derived by decomposing the entire decoder into several decoding modules (DM), and identifying the fundamental operation unit (termed complexity unit or CU) in each DM. The complexity of each DM is modeled by the product of the average complexity of one CU and the number of CUs required. The model is shown to be highly accurate for software video decoding both on Intel Pentium mobile 1.6-GHz and ARM Cortex A8 600-MHz processors, over a variety of video contents at different spatial and temporal resolutions and bit rates. We further show how to use this model to predict the required clock frequency and hence perform dynamic voltage and frequency scaling (DVFS) for energy efficient video decoding. We evaluate achievable power savings on both the Intel and ARM platforms, by using analytical power models for these two platforms as well as real experiments with the ARM-based TI OMAP35x EVM board. Our study shows that for the Intel platform where the dynamic power dominates, a power saving factor of 3.7 is possible. For the ARM processor where the static leakage power is not negligible, a saving factor of 2.22 is still achievable.