•A KNN algorithm is employed for diagnosing the stage of lung cancer disease.•A genetic algorithm is hybridized for an efficient feature selection.•The best value for K is determined using an experimental procedure.•The implementation on a long cancer database reveals 100% accuracy.•The proposed approach requires the least CPU time among four. Lung cancer is one of the most common diseases for human beings everywhere throughout the world. Early identification of this disease is the main conceivable approach to enhance the possibility of patients’ survival. In this paper, a k-Nearest-Neighbors technique, for which a genetic algorithm is applied for the efficient feature selection to reduce the dataset dimensions and enhance the classifier pace, is employed for diagnosing the stage of patients’ disease. To improve the accuracy of the proposed algorithm, the best value for k is determined using an experimental procedure. The implementation of the proposed approach on a lung cancer database reveals 100% accuracy. This implies that one could use the algorithm to find a correlation between the clinical information and data mining techniques to support lung cancer staging diagnosis efficiently.