Malignant melanoma (MM) is one of the most dangerous skin cancers. The aim of this study was to present a potential new method for the differential diagnosis of MM from melanocytic naevi (MN). We examined 20 MM and 19 MN with a new ultra-high-frequency ultrasound (UHFUS) equipped with a 70 MHz linear probe. Ultrasonographic images were processed for calculating 8 morphological parameters (area, perimeter, circularity, area ratio, standard deviation of normalized radial range, roughness index, overlap ratio and normalized residual mean square value) and 122 texture parameters. Colour Doppler images were used to evaluate the vascularization. Features reduction was implemented by means of principal component analysis (PCA), and 23 classification algorithms were tested on the reduced features using histological response as ground-truth. Best results were obtained using only the first component of the PCA and the weighted k-nearest neighbour classifier; this combination led to an accuracy of 76.9%, area under the ROC curve of 83%, sensitivity of 84% and specificity of 70%. The histological analysis still remains the gold-standard, but the UHFUS images processing using a machine learning approach could represent a new non-invasive approach.