Histogram equalization (HE), a simple contrast enhancement (CE) method, tends to show excessive enhancement and gives unnatural artifacts on images with high peaks in their histograms. Histogram-based CE methods have been proposed in order to overcome the drawback of HE, however, they do not always give good enhancement results. In this letter, a histogram-based locality-preserving CE method is proposed. The proposed method is formulated as an optimization problem to preserve localities of the histogram for performing image CE. The locality-preserving property makes the histogram shape of the enhanced image to be similar to that of the original image. Experimental results show that the proposed histogram-based method gives output images with graceful CE on which existing methods give unnatural results.