Image classification is an important task in computer vision, but it is very challenging due to image variations, such as viewpoint, scale and deformation. Feature extraction is a key component of image classification, which can reduce the dimensionality of the image. However, traditional feature extraction methods require domain experts to design. Recently, evolutionary deep learning approaches have gained success in feature learning and image classification. However, the majority of these approaches such as CNNs are data driven and computationally expensive. The potential of the Evolutionary Computation (EC) approaches on the basis of deep learning ideas for image classification has not been extensively investigated. Genetic Programming (GP) as an EC technique, has very good search ability, flexible representation and good interpretability. However, the work on using GP to design evolutionary deep learning approaches is rare. The goal of this work is to explore the potential of GP and improve its performance on different image classification tasks. This will be achieved by developing a new GP approach to region detection, feature extraction, feature construction, and image classification, a new GP method with deep structures to feature extraction for image classification with a small number of training instances, an effective local search method in GP with deep structures, and new transfer learning approaches in GP with deep structures.