This study proposes damage detection algorithms for multistory shear structures that only need the first two or three natural frequencies. The methods are able to determine the location and severity of damage on the basis of damage location indices (DLI) and damage quantification indices (DQI) consisting of the changes in the first few squared natural frequencies of the undamaged and damaged states. The damage is assumed to be represented by a reduction in stiffness. This stiffness reduction causes a shift in the natural frequencies of the structure. The uncertainty associated with system identification methods for obtaining natural frequencies is also carefully considered. The methods are accurate and cost-effective means only requiring the changes in the natural frequencies.