The common techniques used to implement image steganography are: One-Modified Least Significant Bits (LSB) substitution techniques with the readjustment procedure to reduce the Mean Square Error (MSE); Two-Pixel Indicator (PI) to increase the complexity of embedding procedure; Three-random path inside the file. These techniques, when used without making much compromise on the critical parameters, ensure enhanced security of the secret data. In this study, we propose to effectuate the knight's tour for random walk without altering the quality of the image. To ensure full security, randomization of the Red, Green and Blue (RGB) planes of the cover image using row vector is implemented and the obtained image is divided into four pixel blocks. Then, knight's tour to choose successive block follows the Pixel Value Differencing (PVD) to embed data optimally. Thus, this method assures a highly imperceptible and complex steganography with higher capacity. © 2013 Academic Journals Inc.