Progress in the discovery of new materials has been accelerated by the development of reliable quantum-mechanical approaches to crystal structure prediction. The properties of a material depend very sensitively on its structure; 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 optimization and relying on little or no empirical knowledge, have been used to study crystalline structures, point defects, surfaces and interfaces. In this Review, we discuss structure prediction methods, examining their potential for the study of different materials systems, and present examples of computationally driven discoveries of new materials — including superhard materials, superconductors and organic materials — that will enable new technologies. Advances in first-principle structure predictions also lead to a better understanding of physical and chemical phenomena in materials.