A new sensitivity approach for detecting bridge deterioration using the mean-squared response is proposed, in which the dynamic responses of the bridge are estimated using a vehicle-bridge dynamic interaction model. The sensitivity of the mean-squared response to bridge damage is investigated and matrices are generated by defining the stiffness variation of the bridge element as an index of damage factor. The mean-squared response sensitivity method detects local bridge damage with significantly fewer iteration times, and the identification accuracy is proportional to the number of measuring points. The mean-squared response sensitivity approach may correctly identify bridge local damage, including single-element and two-element damage.