In this paper we investigate using multi-objective genetic programming to evolve a feature extraction stage for multiple-class classifiers. We find mappings which transform the input space into a new, multi-dimensional decision space to increase the discrimination between all classes; the number of dimensions of this decision space is optimized as part of the evolutionary process. A simple and fast multi-class classifier is then implemented in this multi-dimensional decision space. Mapping to a single decision space has significant computational advantages compared to k-class-to-2-class decompositions; a key design requirement in this work has been the ability to incorporate changing priors and/or costs associated with mislabeling without retraining. We have employed multi-objective optimization in a Pareto framework incorporating solution complexity as an independent objective to be minimized in addition to the main objective of the misclassification error. We thus give preference to simpler solutions which tend to generalize well on unseen data, in accordance with Occam's Razor. We obtain classification results on a series of benchmark problems which are essentially identical to previous, more complex decomposition approaches. Our solutions are much simpler and computationally attractive as well as able to readily incorporate changing priors/costs. In addition, we have also applied our approach to the KDD-99 intrusion detection dataset and obtained results which are highly competitive with the KDD-99 Cup winner but with a significantly simpler classification framework.