Skin cancer is a spreading disease in the western world. Early detection and treatment are crucial for improving the patient survival rate. In this paper we present two algorithms for computer assisted diagnosis of melanomas. The first is the support vector machines algorithm, a state-of-the-art large margin classifier, which has shown remarkable performances on object recognition and categorization problems. The second method, spin glass-Markov random fields, combines results of statistical physics of spin glasses with Markov random fields. We compared the two approaches using color histograms as features. We benchmarked our methods with another algorithm presented in the literature, which uses a sophisticated segmentation technique and a set of features especially designed for melanoma recognition. To our knowledge, this algorithm represents the state of the art on skin lesions classification. We show with extensive experiments that the support vector machines approach outperforms the existing method and, on two classes out of three, it achieves performances comparable to those obtained by expert clinicians.