Bridge damage detection using vibration data has been confirmed as a promising approach. Compared to the traditional method that typically needs to install sensors or systems directly on bridges, the drive-by bridge damage detection method has gained increasing attention worldwide since it just needs one or a few sensors instrumented on the passing vehicle. Bridge frequencies extracted from the vehicle’s vibrations can be good references for damage detection. However, extant literature considered mainly low-frequency responses of the vehicle, while the high-frequency responses that also contained the bridge’s damage information were often ignored. To fill this gap, this paper developed a damage detection approach that utilized both low and high-frequency responses of the passing vehicle. Mel-frequency cepstral coefficients (MFCCs) and support vector machine (SVM) were employed to classify damage severity. Firstly, the vehicle’s frequency responses are utilized as input features to train SVM models to identify the bridge’s condition. Then, to reduce dimensions of inputs and improve training efficiency, frequency responses are projected from the Hertz scale into the Mel scale, and two means using MFCCs are used to feed different SVM models. A laboratory experiment with a U-shaped continuous beam and a model car was used to verify the effectiveness of the proposed method. Results showed that high-frequency responses contain much information about the bridge’s conditions, and using MFCCs could apparently improve computational efficiency. The errors of damage detection when a heavy car was employed were within 5%.