Heart sound classification plays a vital role in the early detection of cardiovascular disorders, especially for small primary health care clinics. Despite that much progress has been made for heart sound classification in recent years, most of them are based on conventional segmented features and shallow structure based classifiers. These conventional acoustic representation and classification methods may be insufficient in characterizing heart sound, and generally suffer from a degraded performance due to the complicated and changeable cardiac acoustic environment. In this paper, we propose a new heart sound classification method based on improved Mel-frequency cepstrum coefficient (MFCC) features and convolutional recurrent neural networks. The Mel-frequency cepstrums are firstly calculated without dividing the heart sound signal. A new improved feature extraction scheme based on MFCC is proposed to elaborate the dynamic characteristics among consecutive heart sound signals. Finally, the MFCC-based features are fed to a deep convolutional and recurrent neural network (CRNN) for feature learning and later classification task. The proposed deep learning framework can take advantage of the encoded local characteristics extracted from the convolutional neural network (CNN) and the long-term dependencies captured by the recurrent neural network (RNN). Comprehensive studies on the performance of different network parameters and different network connection strategies are presented in this paper. Performance comparisons with state-of-the-art algorithms are given for discussions. Experiments show that, for the two-class classification problem (pathological or non-pathological), a classification accuracy of 98% has been achieved on the 2016 PhysioNet/CinC Challenge database.