Over the last few decades, model updating has become popular in structural dynamics, as it can be used to calibrate (finite element) models, with applications in assessing whether damage has occurred in a structural health monitoring context. Early approaches focused on determining the “best” fitting model in a deterministic manner. For example, mathematical optimisation was employed to minimise the discrepancy between measured and simulated modal parameters. More up-to-date approaches take uncertainties, e.g., due to measurement errors or model discrepancy, into account. In this context, Bayesian model updating has become increasingly popular. Recently, “likelihood-free” approaches have been proposed as an alternative to (exact) Bayesian model updating, with Bayesian history matching (BHM) being a promising “likelihood-free” technique. However, since BHM is based on an approximation of the simulation model using a Gaussian process regression (GPR), it can become inaccurate for highly non-linear and especially for (quasi-)discontinuous problems. Therefore, in this work, a new non-implausibility-motivated optimisation (NIMO) approach is proposed, which overcomes the non-linear space problem. The method is a combination of global optimisation and GPR. Global optimisation is used to accurately determine a non-implausible region in the design space, even for discontinuous problems. Subsequently, a GPR is fitted within the non-implausible region to efficiently approximate a posterior distribution. First, the NIMO approach is verified using test functions. Second, a validation is conducted by localising damage on a laboratory beam structure. It is demonstrated that the NIMO approach yields more robust results compared to BHM, while its computing times are manageable and – depending on the objective function – even smaller compared to BHM.