Progress in the discovery of new materials has recently been driven by the development of reliable quantum-mechanical approaches to crystal structure prediction. The properties of a material depend very sensitively on its structure, and therefore structure prediction is the key to computational materials discovery. Structure prediction was considered to be a formidable problem, but the development of new computational tools has allowed the structures of many new and increasingly complex materials to be anticipated. These widely applicable methods, based on global optimisation and relying on little or no empirical knowledge, have been used to study crystalline structures, point defects, surfaces and interfaces. In this review we present examples of computationally-driven discovery of new materials that will enable new technologies and lead to a better understanding of physical and chemical phenomena in materials.