Minimization of perceptual and statistical distortions is one of the main challenges facing steganographic schemes. The most common approach to minimizing perceptual distortion is Least Significant Bit embedding. However, the statistical features (e.g., histogram) of the stego-images may be changed significantly even with selection of the regions of interest in the embedding process. This opens security gaps for steganal-ysis. To address this issue in this paper, we propose a novel steganographic algorithm, which is capable of preserving the histogram of the cover images in the stego-images and minimizing visual distortions. We partition the gray intensity scale into small segments and only allow the embedding process to modulate the gray intensity within the same segment. Randomization is employed to ensure the preservation of the histogram of cover images.