Bridge health monitoring is a very important part for infrastructure maintenance. Traditional bridge health monitoring techniques require sensors to be installed on bridges, which is costly and time consuming. In order to resolve this issue, new damage detection techniques by installing sensors on passing-by vehicles on bridges and considering vehicle bridge interaction (VBI) have gained much attention from researchers in last decade. In this paper, a novel damage detection technique utilizing data collected from sensors mounted on a large number of passing-by vehicles is developed. First, an approach based on Mel-frequency cepstral coefficients (MFCCs) is introduced. Then, an improved version based on MFCCs and principal component analysis (PCA) taking advantage of mobile sensor network is proposed to overcome the deficiencies in the approaches that utilize single measurement. In the improved approach, the acceleration data is first collected from all the vehicles within a certain period. Then, the transformed features that are related to bridge damage are extracted from MFCCs and PCA. The damage can be identified by comparing the distributions of these transformed features. The results from the numerical analysis and lab experiments show that the approach not only identifies the existence of the damage, but also provides useful information about severity.