Feature extraction is an essential process in the intelligent fault diagnosis of rotating machinery. Although existing feature extraction methods can obtain representative features from the original signal, domain knowledge and expert experience are often required. In this article, a novel diagnosis approach based on evolutionary learning, namely, automatic feature extraction and construction using genetic programming (AFECGP), is proposed to automatically generate informative and discriminative features from original vibration signals for identifying different fault types of rotating machinery. To achieve this, a new program structure, a new function set, and a new terminal set are developed in AFECGP to allow it to detect important subband signals and extract and construct informative features, automatically and simultaneously. More important, AFECGP can produce a flexible number of features for classification. Having the generated features, k -Nearest Neighbors is employed to perform fault diagnosis. The performance of the AFECGP-based fault diagnosis approach is evaluated on four fault diagnosis datasets of varying difficulty and compared with 14 baseline methods. The results show that the proposed approach achieves better fault diagnosis accuracy on all the datasets than the competitive methods and can effectively identify different fault conditions of rolling bearing, gear, and rotor.