This work proposes a reversible data hiding algorithm that is based on the median difference histogram. The method divides the cover image into non-overlapping identical blocks. In each block, the median pixel is selected to calculate absolute differences between the median pixel value and the values of the other pixels. Then, these differences are used to generate a histogram and the histogram shifting method is adopted to embed data. The method can reduce the values of differences and increase the maximum frequency of the histogram. Therefore, the hiding capacity can be increased. Experimental results are presented to prove the validity of the proposed algorithm.