Reduction of the error rate of melanoma diagnosis, a critical and very dangerous skin cancer that could be treated when early detected, is of major importance. Towards this direction, the present paper presents a novel ensemble classification technique, combining traditional Random Forests with the `Markov Blanket' notion. The proposed algorithm performs an inherent feature selection phase where only truly informative features are carried forward, thus alleviating the curse of dimensionality and augmenting classification performance. It has been evaluated in a high-dimensional and imbalanced dataset of 1041 skin lesion images, which been preprocessed using the ABCD-rule of dermatology. The proposed ensemble classification technique exhibited a higher classification performance in comparison with the classical Random Forest algorithms, as well as other widely-used classification algorithms where standard feature reduction techniques, such as PCA and SVD, have been applied.