This paper presents a damage assessment procedure applied to periodic spring mass systems using an eigenvalue sensitivity-based method. The damage is directly related to the stiffness reduction of the damage element. The natural frequencies of periodic structures with one single disorder are found by adopting the transfer matrix approach, consequently, the first order approximation of the natural frequencies with respect to the disordered stiffness in different elements is used to form the sensitivity matrix. The analysis shows that the sensitivity of natural frequencies to damage in different locations depends only on the mode number and the location of damage. The stiffness changes due to damage can be identified by solving a set of underdetermined equations based on the sensitivity matrix. The issues associated with many possible damage locations in large structural systems are addressed, and a means of improving the computational efficiency of damage detection while maintaining the accuracy for large periodic structures with limited available measured natural frequencies, is also introduced in this paper. The incomplete measurements and the effect of random error in terms of measurement noise in the natural frequencies are considered. Numerical results of a periodic spring-mass system of 20 degrees of freedom illustrate that the proposed method is simple and robust in locating single or multiple damages in a large periodic structure with a high computational efficiency.