Lung cancer is one of the leading causes of death world wide. Several computer-Aided diagnosis systems have been developed to help reduce lung cancer mortality rates. This paper presents a novel structural co-occurrence matrix (SCM)-based approach to classify nodules into malignant or benign nodules and also into their malignancy levels. The SCM technique was applied to extract features from images of nodules and classifying them into malignant or benign nodules and also into their malignancy levels. The computed tomography exams from the lung image database consortium and image database resource initiative datasets provide information concerning nodule positions and their malignancy levels. The SCM was applied on both grayscale and Hounsfield unit images with four filters, to wit, mean, Laplace, Gaussian, and Sobel filters creating eight different configurations. The classification stage used three well-known classifiers: multilayer perceptron, support vector machine, and $k$-nearest neighbors algorithm and applied them to two tasks: ( $i$ ) to classify the nodule images into malignant or benign nodules and ( $ii$ ) to classify the lung nodules into malignancy levels (1 to 5). The results of this approach were compared to four other feature extraction methods: gray-level co-occurrence matrix, local binary patterns, central moments, and statistical moments. Moreover, the results here were also compared to the results reported in the literature. Our approach outperformed the other methods in both tasks; it achieved 96.7% for both accuracy and F-Score metrics in the first task, and 74.5% accuracy and 53.2% F-Score in the second. These experimental results reveal that the SCM successfully extracted features of the nodules from the images and, therefore may be considered as a promising tool to support medical specialist to make a more precise diagnosis concerning the malignancy of lung nodules. © 2013 IEEE.