This paper proposes a novel temporal distortion cost (TDC) for sample adaptive offset (SAO) filter in High Efficiency Video Coding. The TDC addresses the images with temporal distortion by evaluating the errors between pre/post-SAO samples and raw samples in continuous frames. Due to high computational complexity of TDC, we further propose a low-complexity TDC (L-TDC) to estimate the value of TDC by a difference classification scheme and a rate-distortion decision scheme. We also contribute to deriving a spatio-temporal distortion cost (STDC) and a low-complexity STDC (L-STDC) by incorporating a spatial distortion cost into the proposed TDCs. Simulation results show that, compared to the classical SAO filter, the proposed SAO filters can save up to around 10% ∼ 15% bitrates under the same flicker measure, and achieve better flicker measure with over 10% improvement in average under the same bitrate. Some valuable threshold analyses are also provided.