The C-fuzzy decision tree (CFDT)–based on the fuzzy C-means (FCM) algorithm has been proposed recently. In many experiments, the CFDT performs better than the “standard” decision tree, namely, the C4.5. A new C-fuzzy decision tree (NCFDT) is proposed, and it outperforms the CFDT. Two design issues for NCFDT are as follows. First, the growing method of NCFDT is based on both classification error rate and the average number of comparisons for the decision tree, whereas that of CFDT only addresses classification error rate. Thus, the proposed NCFDT performs better than the CFDT. Next, the classified point replaces the cluster center to classify the input vector in the NCFDT. The classified-points searching algorithm is proposed to search for one classified point in each cluster. The classification error rate of the NCFDT with classified points is smaller than that of CFDT with cluster centers. Furthermore, these classified points can be applied to the CFDT to reduce classification error rate. The performance of NCFDT is compared to CFDT and other methods in experiments.