Feature construction and feature selection are crucial techniques in machine learning, pattern recognition, and data mining. These processes aim to enhance the quality of features and reduce the data’s dimensionality, ultimately leading to more accurate classification outcomes. In this study, we propose a two-stage hybrid feature construction and feature selection method called H-GPFCWFS for classification tasks. H-GPFCWFS consists of two stages: a multiple feature construction stage based on Genetic Programming (GP) and a feature selection stage using the Whale Optimization Algorithm (WOA). GP’s flexible representation ability and WOA’s search capability are effectively combined in H-GPFCWFS. Additionally, we design a new fitness function to evaluate the individuals’ performance during the GP evolution process. Experimental results show that H-GPFCWFS outperforms four state-of-the-art methods on twelve datasets.