In this study, a machine learning-based approach, which consists of segmentation, feature extraction and classification stages sequentially, is proposed that could help physicians while evaluating the phonocardiogram (PCG) records. In the segmentation stage, an algorithm that uses Mel-frequency cepstral coefficients combined with wavelet transform is adopted. Five different features obtained from time and statistics domain were determined to be used in the classification stage. A two-level classification structure is introduced using three different classifiers, namely the multilayer perceptron (MLP), the k nearest neighbors (k-NN) and support vector machine (SVM). While at the first level it is aimed to classify normal and abnormal PCG records; at the second level it is aimed to classify abnormal PCG records as aortic valve stenosis (AS) and mitral valve regurgitation (MR).