Bridges are vital components of transport infrastructures, and therefore, it is of utmost importance that they operate safely and reliably. This paper proposes and tests a methodology for detecting and localizing damage in bridges under both traffic and environmental variability considering non-stationary vehicle-bridge interaction. In detail, the current study presents an approach to temperature removal in the case of forced vibrations in the bridge using principal component analysis, with detection and localization of damage using an unsupervised machine learning algorithm. Due to the difficulty in obtaining real data on undamaged and later damaged bridges that are simultaneously influenced by traffic and temperature changes, the proposed method is validated using a numerical bridge benchmark. The vertical acceleration response is derived from a time-history analysis with a moving load under different ambient temperatures. The results show how machine learning algorithms applied to bridge damage detection appear to be a promising technique to efficiently solve the problem’s complexity when both operational and environmental variability are included in the recorded data. However, the example application still shows some limitations, such as the use of a numerical bridge and not a real bridge due to the lack of vibration data under health and damage conditions, and with varying temperatures; the simple modeling of the vehicle as a moving load; and the crossing of only one vehicle present in the bridge. This will be considered in future studies.