Damage detection is important to detect and identify damage in structures to avoid catastrophic failures or to take preventive measures. Damage detection using model updating has been attempted in many studies. However, one of the problems that has not been much addressed is the severe under-determinacy of the test data available with very large no. of damage sites that are possible. The problem becomes more sever in real-life structures which are often large and complex. To address this issue, a method for damage detection is proposed in this paper in which damage is identified in substructures and progressively the substructures with no damage are eliminated from the successive cycles of damage detection. A finer sub-structuring of the substructures with damages is further done to localize the dam-age and make an assessment of the damage. A multi-objective function based on natural frequency error and MAC based correlation is minimized and changes in the coefficients of the substructure stiffness matrices are interpreted in terms of the damages. A numerical study of damage detection in a beam using a 3D solid finite element model is presented to validate the method.