The piezoelectric impedance-based damage identification, which traditionally uses the inverse optimization with sensitivity matrix, can in theory identify the damage location and damage severity at the same time. However, the inverse problem is underdetermined in most cases, since the number of unknowns (i.e., possible damage locations and severities) is far more than that of useful measurements. Recently, a new damage identification strategy has been proposed, which is based on Bayesian inference framework. This strategy necessitates employing forward analysis-based instead of inverse-based identification procedures. As the Bayesian inference is sampling-based algorithm, it requires repeated evaluation (FEA analysis) in the parameter space. Since in most cases, one has no prior information on the damage location and severity, the Bayesian inference should be carried out in a large parameter space that will need extremely high computing cost. In this research, a robust and efficient damage identification procedure by employing piezoelectric impedance is developed by combining the sensitivity matrix analysis and the Bayesian inference framework. The new procedure includes two steps. In the first step, a group of possible damage locations and corresponding severity are predicted based on sensitivity matrix analysis, which however does not require solving the inverse of the sensitivity matrix. The prediction from the first step is then used as the sample space. Subsequently, Bayesian inference is carried out to further determine the damage location and severity. Numerical simulations are carried out to demonstrate the damage identification performance.