Structural condition assessment methods based on evolutionary algorithms (EAs) may suffer slow calculation efficiency problems as they are required to substitute into the finite element models repeatedly. The repeat finite element (FE) model analysis greatly restricts their applications to complex civil infrastructures. To this end, we propose an incremental Kriging surrogate model to significantly raise calculation efficiency during the structural condition assessment. Furthermore, to further utilize the colony information in EAs, a one-step K-means clustering strategy is applied to generate several clustering centers individuals. These individuals and the most promising one determined by the Kriging surrogate model will be substituted into the FE model-based objective function and then sent to the Kriging model again to realize online learning and training. The proposed novel algorithm can achieve the balance between the calculation accuracy and efficiency as the Kriging model is trained incrementally and the algorithm only evaluates the promising and clustering center individuals in each generation. Then, the proposed algorithm is used to carry out damage identification or FE model updating for the Canton Tower, a cantilever beam, and a real bridge as verification studies. This work provides a reference for introducing online Kriging learning and novel model management mechanisms in EA-based FE model updating or structural condition assessment.