Reversible data hiding (RDH) is a special kind of data hiding technique which can exactly recover the cover image from the stego image after extracting the hidden data. Recently, Wu et al. proposed a novel RDH method with contrast enhancement (RDH-CE). RDH-CE achieved a good effect in improving visual quality especially for poorly illustrated images. In Wu’s method, however, the PSNR of stego image is relatively low and embedding performance is largely influenced by the histogram distribution of cover image. Since PSNR is still considered as one of the most important metrics for evaluating the RDH performance, this paper presents a reliable RDH method based on adaptive histogram shifting for gray-scale images to improve the PSNR of stego image while maintaining the good effect of the contrast enhancement obtained by RDH-CE.