While a healthy human heart produce a rhythmic pattern of sounds, some heart disorder induce deviations perceived as abnormal sounds called murmurs. Despite many murmurs can be considered harmless, other constitute the first basis of a heart disorder. In this sense, a correct diagnosis remains essential; however, due to the subjectivity on using human ear to make diagnosis, automatic detection systems appear as useful tools for helping medical specialists on improving diagnosis accuracy. Complexity analysis has become one important tool for the study of physiological signals, because tracking sudden alteration on the inherent complexity on biological processes might be useful for detecting pathologies. The present paper presents a complexity-based analysis methodology, which uses regularity features for the detection of heart murmurs, including Approximate Entropy, Sample Entropy, Gaussian Kernel Approximate Entropy, and Fuzzy Entropy. The results show the high discriminative power, up to 90%, of the Gaussian Kernel Approximate Entropy and Fuzzy Entropy for the proposed labour.