This paper presents a probabilistic approach to evaluate the small-signal stability of power systems in the presence of time delays. An exact method is proposed to determine the functional relationship between delay margin for stability and system parameters. The delay margin is modeled as a random variable and its probability density function (PDF) is estimated based on the PDF of the load using a Monte Carlo simulation approach. The probability of stability for a given time delay is determined using the estimated PDF of the delay margin. For illustration purposes, the method is applied to a single-machine-infinite bus (SMIB) power system with an exciter. The probability of stability for a given time delay is computed and their sensitivity with respect to various system parameters is investigated. It is found that the probability of stability values reduce with increasing the load uncertainty resulting in a less stable system while the stability performance could be improved by increasing the generator transient reactance. Moreover, the effect of generating damping on the probability of stability is relatively complex and larger damping may not result in a more stable operation. Copyright (C) 2010 Praise Worthy Prize S.r.l. - All rights reserved.