The identification of materials with exceptional properties is an essential objective to enable technological progress. We propose the application of \textit{Quality-Diversity} algorithms to the field of crystal structure prediction. The objective of these algorithms is to identify a diverse set of high-performing solutions, which has been successful in a range of fields such as robotics, architecture and aeronautical engineering. As these methods rely on a high number of evaluations, we employ machine-learning surrogate models to compute the interatomic potential and material properties that are used to guide optimisation. Consequently, we also show the value of using neural networks to model crystal properties and enable the identification of novel composition--structure combinations. In this work, we specifically study the application of the MAP-Elites algorithm to predict polymorphs of TiO$_2$. We rediscover the known ground state, in addition to a set of other polymorphs with distinct properties. We validate our method for C, SiO$_2$ and SiC systems, where we show that the algorithm can uncover multiple local minima with distinct electronic and mechanical properties.