In this paper we propose a new method of hiding information that produces a stego-image which is totally indistinguishable from the original image to extract the hiding message. GA is used as an efficient method to minimize the number of different bits between the cover image and the stego-image as minimum as possible by embedding the message in random locations of cover image, and then modifying the locations containing changed information in original image (cover) to improve stego-image quality. To satisfy excellent security we used a crypto-key which contains encrypted locations from hiding process. This key is used to extract the embedded message.