Reversible watermarking inserts watermarks into digital media in such a way that visual transparency is preserved, which enables the restoration of the original media from the watermarked one without any loss of media quality. It has various applications where high capacity and high visual quality are major requirements for reversible watermarking. This work presents a new reversible watermarking algorithm that embeds message bits by modifying the differential histogram of adjacent pixels. To satisfy both high embedding capacity and visual quality, the proposed technique exploits the fact that the adjacent pixels are highly correlated. Also, we prevent overflow and underflow problems by designing a predicted error compensation scheme. Through experiments using multiple kinds of test images, we prove that the presented algorithm provides 100% reversibility, higher capacity, and higher visual quality than any previous method, while maintaining low induced distortion.