To meet the need for reliable real-time monitoring of civil structures, safety control and optimization of maintenance operations, this paper presents a computational method for the stochastic estimation of the degradation of the load bearing structural properties. Exploiting a Bayesian framework, the procedure sequentially updates the posterior probability of the damage parameters used to describe the aforementioned degradation, conditioned on noisy sensors observations, by means of Markov chain Monte Carlo (MCMC) sampling algorithms. To enable the analysis to run in real-time or close to, the numerical model of the structure is replaced with a data-driven surrogate used to evaluate the conditional likelihood. The proposed surrogate model relies on a Multi-Fidelity (MF) Deep Neural Network (DNN), mapping the damage and operational parameters onto approximated sensor recordings. The MF-DNN is shown to effectively leverage information between multiple datasets, by learning the correlations across models with different fidelities without any prior assumption, ultimately alleviating the computational burden of the supervised training stage. The Low Fidelity (LF) responses are approximated by relying on proper orthogonal decomposition for the sake of dimensionality reduction, and a fully connected DNN. The high fidelity signals, that feed the MCMC within the outer-loop optimization, are instead generated by enriching the LF approximations through a deep long short-term memory network. Results relevant to a specific case study demonstrate the capability of the proposed procedure to estimate the distribution of damage parameters, and prove the effectiveness of the MF scheme in outperforming a single-fidelity based method.