Steganography is the art and science of secret communication. Various types of media, such as images, videos, audio etc. can be used to hide the message. This paper presents an approach to steganography using LBP on a cluster formed by the CIELAB (Informally called Lab) based k-means clustering. Image Steganography embeds the secret message into the images exclusively. Basically Image Steganography uses LSB of pixels to embed the message, but this lone technique is easily detectable, so LBP is the technique which is used in the approach to embed data into image. It uses the pattern classification characteristics to modify the values of pixels in such a way that the modification yields the message requirements and aids the extraction process. But using pure LBP is also detectable and messages can be retrieved. Even to secure the location of LBP hidden message in the image, segmentation is used for hiding the using only desired areas of the image. For segmentation various clustering techniques can be implemented. For the purpose k-means clustering is used, which provides better accuracy for huge data sets. The images have huge number of pixels and every pixel further has 3 components namely red, green and blue for color images. So k-means clustering serves the purpose even concerning the speed. For k-means clustering using Lab color space adds its own advantages, as Lab color space approximates human vision.