We present a data-driven approach based on physical insights to achieve damage diagnosis of bridges using only vibration signals collected on board the vehicles passing over the bridge. Though data-driven models have been shown to produce promising results in this context, they generally require labeled examples to fit the models (i.e., supervised learning) and make it difficult to interpret the physical mechanisms. We posit that these shortcomings can be alleviated by studying the physical relationship between damage and the distribution of the resulting acceleration signals, and then choosing an appropriate model to invert this process. To help guide the development of appropriate damage diagnosis algorithms, we first make use of the theoretical formulation of the vehicle-bridge interaction system in the frequency domain and conduct a finite element simulation of this system. From the derived numerical solution, we observe that not only is the trend of the acceleration signals of a passing vehicle with different damage severity non-linear, but also that both the low- and high-frequency responses of a passing vehicle contain information about damage severity. Guided by these observations, we use several dimensionality reduction methods to extract representative features from the vehicle’s vibration response. We then propose an unsupervised damage severity comparison model and a semi-supervised damage severity estimation model aiming at indirect monitoring of bridges. We apply the algorithms to diagnose changes that occur in a laboratory bridge model to which a concentrated mass of gradually changing magnitude is attached at mid-span. The experimental results of the damage severity comparison and estimation show that a non-convex and non-linear dimensionality reduction technique (stacked autoencoders) outperforms other linear and/or convex dimensionality reduction techniques. Overall, our results provide evidence for the applicability of indirect structural health monitoring in bridge models and suggest the feasibility of extending this approach to actual structures.