ABSTRACTCrystal structure predictions based on first-principles calculations have gained great success in materials science and solid state physics. However, the remaining challenges still limit their applications in systems with a large number of atoms, especially the complexity of conformational space and the cost of local optimizations for big systems. Here, we introduce a crystal structure prediction method, MAGUS, based on the evolutionary algorithm, which addresses the above challenges with machine learning and graph theory. Techniques used in the program are summarized in detail and benchmark tests are provided. With intensive tests, we demonstrate that on-the-fly machine-learning potentials can be used to significantly reduce the number of expensive first-principles calculations, and the crystal decomposition based on graph theory can efficiently decrease the required configurations in order to find the target structures. We also summarized the representative applications of this method on several research topics, including unexpected compounds in the interior of planets and their exotic states at high pressure and high temperature (superionic, plastic, partially diffusive state, etc.); new functional materials (superhard, high-energy-density, superconducting, photoelectric materials), etc. These successful applications demonstrated that MAGUS code can help to accelerate the discovery of interesting materials and phenomena, as well as the significant value of crystal structure predictions in general.