Negative Bias Temperature Instability (NBTI) has been a reliability concern with CMOS technology scaling. The threshold voltage of a p-MOSFET degrades, resulting in the delay increment of a digital gate since more time is needed to charge the output load. The gate-level timing model takes the threshold voltage shift as an input. Therefore, an accurate and fast simulation method for NBTI is important. In this paper, a new approach to efficiently yet accurately compute the threshold voltage degradation due to AC-mode NBTI is proposed.