Malignant melanoma is the most deadly for of skin lesion. Early diagnosis is of critical importance to patient survival. Visual recognition algorithms could potentially be of great help for physicians in a computer assisted diagnosis system. Previous work on this topic has focused mostly on developing ad-hoc segmentation and feature extraction methods. In this paper we take a completely different approach. We put the emphasis on the learning part of the algorithm by using two kernel-based classifiers, one discriminative and one probabilistic. As a discriminative approach we chose support vector machines, a state of the art large-margin classifier which was proved very successful on visual applications. As a probabilistic approach we chose spin glass-Markov random fields, a kernel Gibbs distribution inspired by results of statistical physics. We benchmarked these algorithms against the (to our knowledge) state-of-the-art method on melanoma recognition, exploring how performance changes by using color or textural features, and how it is affected by the quality of the segmentation mask. We show with extensive experiments that the support vector machine approach outperforms the existing method and, on two classes out of three, it achieves performances comparable to those obtained by expert clinicians