Vibration-based damage detection (VBDD) methods utilize measured changes in the dynamic characteristics of structural systems (natural frequencies, mode shapes, and damping characteristics) to indicate the presence and location of damage. Previous studies have demonstrated that small-scale damage can be reliably located in simple bridge systems when resonant harmonic loading is used as the excitation source for the VBDD measurements. In full-scale bridge applications, however, random loading due to traffic or wind is often more readily achievable. A numerical study was therefore undertaken to investigate the use of random loading for damage detection in a simple-span, slab-on-girder bridge deck. Transient dynamic analyses of a finite element model of the bridge deck subjected to randomly varying loading were performed for nine different simulated small-scale damage states. To reduce the inherent uncertainty arising from the random loading, averaged results from a large number of repeated random trials were used. Several factors that may influence the probability of successfully locating the damage were investigated, including the number of repeated random trials used, the distance from the damage to the nearest sensor, the proximity of the damage to simple supports, the severity of the damage and the presence of random measurement error. It was found that a large number of repeated random trials was required to achieve reasonable probabilities of successfully locating the damage; even then, reliable detection results were not guaranteed for all of the damage conditions considered. Based on these results, therefore, random excitation appears to be less reliable in VBDD than harmonic loading.