Abstract Model updating using measured system dynamic response has a wide range of applications in system response evaluation and control, health monitoring, or reliability and risk assessment. In this paper, we are interested in model updating of a linear dynamic system with non-classical damping based on incomplete modal data including modal frequencies, damping ratios and partial complex mode shapes of some of the dominant modes. In the proposed algorithm, the identification model is based on a linear structural model where the mass and stiffness matrix are represented as a linear sum of contribution of the corresponding mass and stiffness matrices from the individual prescribed substructures, and the damping matrix is represented as a sum of individual substructures in the case of viscous damping, in terms of mass and stiffness matrices in the case of Rayleigh damping or a combination of the former. To quantify the uncertainties and plausibility of the model parameters, a Bayesian approach is developed. A new Gibbs-sampling based algorithm is proposed that allows for an efficient update of the probability distribution of the model parameters. In addition to the model parameters, the probability distribution of complete mode shapes is also updated. Convergence issues and numerical issues arising in the case of high-dimensionality of the problem are addressed and solutions to tackle these problems are proposed. The effectiveness and efficiency of the proposed method are illustrated by numerical examples with complex modes.