In this paper, a new damage detection and quantification method has been presented to perform detection and quantification of structural damage under ambient vibration loadings. To extract modal properties of the structural system under ambient excitation, natural excitation technique (NExT) and eigensystem realization algorithm (ERA) are employed. Sensitivity matrices of the dynamic residual force vector have been derived and used in the parameter subset selection method to identify multiple damaged locations. In the sequel, the steady state genetic algorithm (SSGA) is used to determine quantified levels of the identified damage by minimizing errors in the modal flexibility matrix. In this study, performance of the proposed damage detection and quantification methodology is evaluated using a finite element model of a truss structure with considerations of possible experimental errors and noises. A series of numerical examples with five different damage scenarios including a challengingly small damage level demonstrates that the proposed methodology can efficaciously detect and quantify damage under noisy ambient vibrations.