A novel approach for selecting proper cover images in steganography is presented in this paper. The proposed approach consists of two stages. The first stage is an evolutionary algorithm that extracts the signature of cover images against stego images in the form of fuzzy if-then rules. This algorithm is based on an iterative rule learning approach to construct an accurate fuzzy rule base. The rule base is generated in an incremental way by optimizing one fuzzy rule at a time using an evolutionary algorithm. In the second stage of the proposed approach, the fuzzy rules generated in the first stage are used for selecting suitable cover images for steganography. We applied our approach to some state-of-the-art steganography techniques and validated it using an image database. The results indicate that a secret message can be securely embedded in selected cover images. Therefore, we can apply the proposed evolutionary fuzzy algorithm, as an intelligent rule generation approach, to select the appropriate cover images from an image database and use them to have more secure steganography.