Reversible data hiding for medical image contrast enhancement can not only store patient information imperceptibly, but also improve image contrast quality to facilitate the accurate diagnosis in the remote medical affairs. In this paper, a new reversible data hiding algorithm for medical image contrast enhancement is proposed. The medical image is segmented by the superpixel algorithm, and then the modifications on the region of the interest (ROI) of the image are optimized. Since the image is divided into blocks, the embedded regions can be selectively modified block by block according to their statistical characteristics. Subsequently, the modification of each pixel block applies the classical histogram modification manner, and embeds the payload into multiple embedding points at one time. We take the histogram equalization as the optimization goal, and then reduce the embedding distortion in the process of contrast enhancement. Experimental results show that when compared with the state-of-the-art methods, the proposed method is reversible and can improve the visual quality of medical images in terms of contrast enhancement.