Negative bias temperature instability (NBTI) has become a primary mechanism that degrades performance of integrated circuits. It is well known that NBTI impacts pMOS transistors during circuit operation, and the degradation occurs when pMOS transistor is in a conducting state. So, accurate NBTI degradation analysis requires analysis of logic states. Degradation of specific pMOS transistor depends on part of lifetime, in which this transistor is under stress, in other words, on stress probability. In this paper, we propose the correct algorithm of calculating stress probability for every pMOS transistor of complex CMOS gate. Comparing to simple “naive” approach, our algorithm takes into account two additional factors: correlations between signals at gate inputs, and VDD-potential coming through “bottom” of pMOS transistor. Numerical experiments show the importance of accounting for both these factors.