This paper presents a novel Gibbs sampling approach for structural health monitoring (SHM) with detection of structural changes/damages using incomplete complex modal data measured with a limited number of sensors. The usual difficulty with the availability of sensors in SHM practices and enforcing data acquisition in multiple setups is thoroughly addressed. Structural modeling incorporated with damping is considered in this proposed inverse problem exercise to calibrate damping parameters along with the stiffness and mass parameters facilitating SHM. Both proportional and nonproportional viscous damping are adopted in structural modeling. Detailed formulations on the probabilistic detection of changes/damages are presented in detail. Moreover, a Gibbs sampling technique is introduced to quantify uncertainties of the various sets of uncertain parameters, where samples of the conditional probability density function of a parameter set are obtained iteratively. The proposed approach retains the typical advantage of the nonrequirement of mode-matching. A validation exercise is performed using a three-dimensional building structure (attached with supplementary viscous dampers) and a laboratory steel structure considering multiple damage cases and different sensor placements. The proposed methodology is observed to be efficient for SHM using incomplete complex modal data measured with a limited number of sensors. (C) 2021 American Society of Civil Engineers.