This study employs a novel beam-type wavelet finite element model (WFEM) to fulfill an adaptive-scale damage detection strategy in which structural modeling scales are not only spatially varying but also dynamically changed according to actual needs. Dynamical equations of beam structures are derived in the context of WFEM by using the second-generation cubic Hermite multiwavelets as interpolation functions. Based on the concept of modal strain energy, damage in beam structures can be detected in a progressive manner: the suspected region is first identified using a low-scale structural model and the more accurate location and severity of the damage can be estimated using a multi-scale model with local refinement in the suspected region. Although this strategy can be implemented using traditional finite element methods, the multi-scale and localization properties of the WFEM considerably facilitate the adaptive change of modeling scales in a multi-stage process. The numerical examples in this study clearly demonstrate that the proposed damage detection strategy can progressively and efficiently locate and quantify damage with minimal computation effort and a limited number of sensors.