In this paper, a new histogram-based approach for digital image steganography is introduced. It stems from the idea of utilizing the near maximum values in the image histogram distribution. Conceptually, depending on whether a brightness value with the highest number of occurrence (called as maximum histogram—MH) in the histogram is even or odd, pairs of brightness values next to it are reserved for data embedding. Consequently, data hiding is realized using a pixel pair by employing the LSB technique. Essentially differing from the traditional histogram-based methods in which usually all pixels except from the MH are shifted to create a gap next to the MH of the histogram, the proposed approach does not require such a shifting and largely preserves the visual quality of the cover image. When the number of occurrences is numerically examined in the histograms, it is clear that only three brightness values, (i.e., MH, MH+1 & MH+2 or MH, MH-1 & MH-2), are trivially changed in the stego image. In addition, the MH value information is not necessarily relayed to the recipient since the histogram value of the pixels modified after embedding data is prevented from exceeding the vertex value. Throughout a detailed experimental study, the PSNR results show that the proposed approach not only increases the visual quality of stego images but also makes a reasonably high imperceptibility compared to the similar works in the literature. Considering the proposed HNMH method test results, the PSNR varies between 72.74 and 67.28 dB while the hidden data capacity can be achieved up to 12,759 Bits. The HNMH outperforms its counterparts 3 to 8 times with regard to the data hiding capacity that is almost linearly increased by means of concurrent deployment into the multiple cover image partitions up to a certain saturation point.