The vibration-based damage detection which utilizes measured vibration characteristics to identify structural damage is an inverse problem. In general, the number of potential damage locations is greater than that of available measurements that will result in an underdetermined problem. The conventional vibration-based damage detection methods employ the Tikhonov regularization to deal with this underdetermined problem. The Tikhonov regularization tends to provide over smooth solutions, which causes the identified damage distributed to many structural elements. However, this result does not match the practical situation. Compared with the total elements of the entire structure, structural damage typically occurs at a small number of locations only. In this study, the l1 regularization technique is employed to exploit the sparsity of the structural damage. The sensitivity-based model updating is adopted using frequency and mode shape changes for structural damage detection. Two numerical examples including a cantilever beam and a planar truss are utilized to demonstrate the effectiveness of the proposed sparse damage detection method. The results showed that the proposed sparse damage detection method is effective in identifying single and multiple damages for different types of structures even under the condition of small frequency and mode shape changes. Moreover, the robustness of the proposed method to noise is investigated through simulation studies.