Negative bias temperature instability (NBTI) in PMOS transistors has become a major reliability concern in nanometer scale design, causing the temporal degradation of the threshold voltage of the PMOS transistors, and the delay of digital circuits. A novel method to characterize the delay of every gate in the standard cell library, as a function of the signal probability of each of its inputs, is developed. Accordingly, a technology mapping technique that incorporates the NBTI stress and recovery effects, in order to ensure optimal performance of the circuit, during its entire lifetime, is presented. Our technique, demonstrated over 65 nm benchmarks shows an average of 10 % area recovery, and 12 % power savings, as against a pessimistic method that assumes constant stress on all PMOS transistors in the design.