It is common to estimate structural damage severity by updating a structural model against experimental responses at different damage states. When experimental results from the healthy and damaged states are available, the updated finite element models corresponding to the two states are compared. Updating of these two models occurs sequentially and independently. However, experimental errors, updating procedure errors, modelling errors and parametric errors may propagate and become aggregated in the damaged model in this approach. In this research, a multi-objective genetic algorithm has been proposed to update both the healthy and damaged models simultaneously in an effort to improve the performance of the damage estimation procedure. Numerical simulations of a simply supported beam damaged at multiple locations with noisy mode shapes were considered and improved model updating results were confirmed. It was found that the proposed method is more efficient in accurately estimating damage severity, less sensitive to discretization as well as experimental errors, and gives the analyst an increased confidence in the model updating and damage estimation results.