Deep learning and unsupervised feature learning have received great attention in past years for their ability to transform input data into high level representations using machine learning techniques. Such interest has been growing steadily in the field of medical image diagnosis, particularly in melanoma classification. In this paper, a novel application of deep learning (stacked sparse auto-encoders) is presented for skin lesion classification task. The stacked sparse auto-encoder discovers latent information features in input images (pixel intensities). These high-level features are subsequently fed into a classifier for classifying dermoscopy images. In addition, we proposed a new deep neural network architecture based on bag-of-features (BoF) model, which learns high-level image representation and maps images into BoF space. Then, we examine how using this deep representation of BoF, compared with pixel intensities of images, can improve the classification accuracy. The proposed method is evaluated on a test set of 244 skin images. To test the performance of the proposed method, the area under the receiver operating characteristics curve (AUC) is utilized. The proposed method is found to achieve 95% accuracy.