Negative Bias Temperature Instability (NBTI) has been identified as a major and critical reliability issue for PMOS devices in nano-scale designs. It manifests as a negative threshold voltage shift, thereby degrading the performance of the PMOS devices over the lifetime of a circuit. In order to determine the quantitative impact of this phenomenon an accurate and tractable model is needed. In this paper we ex- plore a novel and practical methodology for modeling NBTI degradation at the logic level for digital circuits. Its major contributions include i) A SPICE level simulation to identify stress on PMOS devices under varying input conditions for various gate types and ii) a gate level simulation method- ology that is scalable and accurate for determining stress on large circuits. We validate the proposed logic level sim- ulation methodology by showing that it is accurate within 1% of the reference model. Contrary to many other papers in this area, our experimental results show that the overall delay degradation of large digital circuits due to NBTI is relatively small.