The last ten years of health care experienced tremendous technological growth, but the mortality rate of patients diagnosed with vocal fold cancer still remains disturbingly static. Therefore, this work is to present a new approach using multi-fractal detrended fluctuation analysis combined with some linear features for the detection and classification of vocal fold cancer patients through speech signals. The authors focus on investigating the combination of nonlinear features from MFDFA with conventional linear features to increase their accuracy in detection. We demonstrate that the combination of these feature sets results in a 3% accuracy improvement when used over the utilization of linear or nonlinear features alone. In addition, the reduced feature set of MFDFA is as good as, and in practice better than, the widely used feature set supplied by the openSMILE toolkit—a further testimony to the efficiency of MFDFA in feature extraction. This was validated on the Saarbruecken Voice Database, showing that it has promise as a practical approach to voice-based detection methods both in clinical and remote environments.