The inconvenience operation of EEG P300 or functional magnetic resonance imaging (FMRI) will be overcome, when the deceptive information can be effectively detected from speech signal analysis. In this paper, the fractional Mel cepstral coefficient (FrCC) is proposed as the speech character for deception detection. The different fractional order can reveal various personalities of the speakers. The linear discriminant analysis (LDA) model (which has the ability of global optimal vector mapping) is introduced, and the performance of FrCC and MFCC in deceptive detection is compared when all the data are mapped to low dimensional. Then, the hidden Markov model (HMM) is introduced as a long-term signal analysis tool. Twenty-five male and 25 female participants are involved in the experiment. The results show that the clustering effect of optimal fractional order FrCC is better than that of MFCC. The average accuracy for male and female speaker is 59.9% and 56.2%, respectively, by using the FrCC under the LDA model. When MFCC is used, the accuracy is reduced by 3.2% and 5.9%, respectively, for male and female. The accuracy can be increased to 71.0% and 70.2% for male and female speakers when HMM is used. Moreover, some individual accuracy is increased over 20%, or even more than 85%, when FrCC is introduced. The results show that the deceptive information is indeed hidden in the speech signals. Therefore, speech-based psychophysiology calculating may be a valuable research field.