Identification of candidate genes responsible for specific phenotypes, such as cancer, has been a major challenge in the field of bioinformatics. Given a DNA Microarray dataset, traditional feature selection methods produce lists of candidate genes which vary significantly under variations of the training data. That instability hinders the validity of research findings and raises doubts about the reliability of such methods. In this study, we propose a framework for the extraction of stable genomic signatures. The proposed methodology enforces stability at the validation step, independent of the feature selection and classification methods used. The statistical significance of the selected gene set is also assessed. The results of this study demonstrate the importance of stability issues in genomic signatures, beyond their prediction capabilities.