Steganography’s role in secret communication extends from concealing information to communication. As one of several possible approaches to embed confidential information in digital images, the Least Significant Bit (LSB) technique has been widely used; however, maintaining the imperceptibility of the stego-image is still a serious concern. In this paper, an Adaptive Random (AR) k-bit embedding approach has been attempted to enhance the quality of stego-images. The original cover is divided into nonoverlapping blocks of equal size. The encrypted confidential data are embedded in each block through four different random walks. The best random walk, which provides the minimum degradation for a particular block, is identified, and is fixed for that block. The decision on the fixed random walk for each block is recorded and kept as the secret key. The AR method has also been combined with the Inverted Pattern approach, referred to as the Adaptive Random Inverted Pattern (ARIP) approach, to further enhance the quality of the stego-image. The estimated Peak Signal to Noise Ratio (PSNR) value for the ARIP method yields 1dB enhancement.