A novel two-step intelligent algorithm is proposed for structural damage detection (SDD) by combining particle swarm optimization and Nelder-Mead (PSO-NM) algorithm, in which two steps are deployed for exploring a better balance between computational efficiency and accuracy. In the first step, a modal strain energy based index (MSEBI) is defined and used to precisely locate damages of structures. In the second step, structural damage extent is determined by PSO-NM algorithm. Some beam-like structures are adopted to assess its applicability. A parametric study and the effect of measurement noise on the method are also considered. The illustrated numerical simulation results show that the novel method can not only locate structural damage but also identify damage extent of beam-like structures with a good robustness to noises.