The purpose of this study is to reconstruct the damage distribution in bridge decks by measuring the noisy response induced by traffic loads. A model-based inverse problem is proposed, where a search algorithm finds the damage parameters that minimize the discrepancy between measurements and simulations that depend on those unknown parameters. Two theoretical contributions are developed and validated: (1) a semi-analytical estimation of the probability of detection, which provides a robust criterion to optimize the positions of sensors, and (2) a measurement filter to maximize the identifiability of damage under noisy measurements, which is also optimized. The two main practical contributions are (1) the feasibility of the proposed model-based inverse problem to reconstruct damage in complex structures such a bridge decks with moving loads under realistic levels of noise and realistic spatial distributions of the structural damage, and (2) the understanding of the complex nature of the damage-deck-moving load interactions provided by a parametric study for different bridge designs, different deck thickness-length ratios, one and two spans and a range of moving load speeds. The feasibility of the proposed inverse problem strategy is validated and shown capable of reconstructing the damage characteristics, with computational efficiency and under realistic levels of noise.