•We present a feature learning scheme for skin lesion image segmentation.•Negative Matrix Factorization is used to generate an initial dictionary and feature set.•A subset of the dictionary atoms is selected to improve compactness and representation.•Normalized Graph Cuts and the learned features are used to segment the input skin lesion image.•The method potentially can be reliable based on experiments and method comparisons. Pre-screening systems for the diagnosis of melanocytic skin lesions depend of the proper segmentation of the image region affected by the lesion. This paper proposes a feature learning scheme that finds relevant features for skin lesion image segmentation. This work introduces a new unsupervised dictionary learning method, namely Unsupervised Information-Theoretic Dictionary Learning (UITDL), and discusses how it can be applied in the segmentation of skin lesions in macroscopic images. The UITDL approach is adaptive and tends to be robust to outliers in the training data, and consists of two main stages. In the first stage, a textural variation image is used to construct an initial feature dictionary and an initial sparse representation via Non-Negative Matrix Factorization (NMF). In the second stage, the feature dictionary is optimized by selecting adaptively the number of dictionary atoms. The greedy approach used for dictionary optimization is quite efficient and flexible enough to be applied to other dictionary learning problems. Furthermore, the proposed method can be easily extended for other image segmentation problems. The experimental results suggest that the proposed approach potentially can provide more accurate skin lesion segmentation results than comparable state-of-the-art methods. The proposed segmentation method could help to improve the performance of pre-screening systems for melanocytic skin lesions, which can affect positively the quality of the early diagnosis provided to skin lesion patients.