Medical image classification develops computational methods for solving problems such as tumour detection in medical images, and their use for biomedical research and clinical care. These methods mainly aim at extracting relevant information or knowledge from medical images that can greatly assist in early detection of a disease which can significantly increase the survival rate of the patient and reduce medical cost. Current techniques vary from applying standard machine learning algorithms to developing new approaches for the needs of the field. Medical images are huge in size, whereas the relevant information is confined in a limited number of features in images. Region detection, feature extraction and feature construction can help significantly reduce the amount of data while improving classification performance by detecting discriminative regions, extracting relevant features, and constructing high-level features, respectively. Existing approaches mostly rely on expert intervention for extracting hand-crafted features while having multiple stages each for preprocessing, feature extraction and classification, which decreases the reliability and increases the computational complexity. Another key limitation faced by existing approaches is interpretability, since a good generalization accuracy is not always the primary objective, and clinicians are interested to analyse specific features responsible for development of the disease; methods that ignore the image structure are not favoured. Therefore, an efficient and effective computational method is required to address these problems. In Evolutionary Computation, Genetic Programming (GP) automatically evolves a model that is interpretable, and allows to deal with the curse of dimensionality (through region detection, feature extraction and feature construction). This thesis aims at developing effective methods for binary and multi-class medical image classification tasks. This will be achieved by developing new GP based approaches to region detection, feature extraction and feature construction, multi-objective classification, and knowledge transfer from different medical domains.