In recent years more and more researchers have done work on Diabetes Mellitus detection through facial image analysis. These methods are non-invasive and convenient to detect Diabetes Mellitus, which are different from the traditional diagnostic methods. In this paper, we propose a new method composed of Gray-scale Histogram Features, Diabetes Mellitus genetic algorithm, and a classifier (k-Nearest Neighbors) with weights to detect Diabetes Mellitus using four facial blocks extracted from the facial image. Firstly, Gray-scale Histogram Features, which represents the distribution of gray-scale values in the image, are extracted from each block to represent it. Next, Diabetes Mellitus genetic algorithm based on genetic algorithm is proposed to select features from the Gray-scale Histogram Features of each block. Finally, k-Nearest Neighbors with weights is used to classify Diabetes Mellitus and Healthy samples. The proposed method is tested on a facial image dataset consisting of 284 Diabetes Mellitus and 142 Healthy samples, which obtains an accuracy of 99.48%.