The structure prediction at the atomic level is emerging as a state-of-the-art approach to accelerate the functionality-driven discovery of materials. By combining the global swarm optimization algorithm with first-principles thermodynamic calculations, it exploits the power of current supercomputer architectures to robustly predict the ground state and metastable structures of materials with only the given knowledge of chemical composition. In this Review, we provide an overview of the basic theory and main features of our as-developed CALYPSO structure prediction method, as well as its versatile applications to design of a broad range of materials including those of three-dimensional bulks, two-dimensional reconstructed surfaces and layers, and isolated clusters/nanoparticles or molecules with a variety of functional properties. The current challenges faced by structure prediction for materials discovery and future developments of CALYPSO to overcome them are also discussed.