The structural health monitoring (SHM) of civil structures and infrastructures is becoming a crucial issue in our smart and hyper-connected age. Due to structural aging and to unexpected loading conditions, partially linked to extreme events caused by the climate change, reliable and real-time SHM schemes are currently facing a burst in development and applications. In this work, we propose a procedure that relies upon a surrogate modeling scheme based on a multi-fidelity (MF) deep neural network (DNN), which has been conceived to sense and identify a structural damage under operational (and possibly environmental) variability. By exploiting the sensor recordings from a densely deployed network within a fully stochastic framework, the MF-DNN model is adopted to feed a Markov chain Monte Carlo sampling procedure and update the probability distribution of the structural state, conditioned on noisy observations. As information regarding the health of real structures is usually rather limited, the datasets to train the MF-DNN are generated with physical (e.g. finite element) models: high-fidelity (HF) and low-fidelity (LF) models are adopted to simulate the structural response under the mentioned varying conditions, respectively in the presence or absence of a structural damage. As far as the architecture of the DNN is concerned, the MF approach is obtained by merging a fully connected LF-DNN and a long short-term memory HF-DNN. The LF-DNN mimics the output of the sensor network in the undamaged condition, while the HF-DNN is exploited to improve the LF model and appropriately catch the structural response in the presence of a pre-defined set of damaged patterns. Thanks to the adaptive enrichment of the LF signals carried out by the MF-DNN, the proposed model updating strategy is reported capable of locating (and possibly quantifying) a damage event.