High pressure can profoundly alter the atomic arrangements, electronic structures, and chemical bonding of condensed matter, providing an important means of tuning material structures and properties and expanding the accessible materials space. Crystal structure prediction (CSP) enables the prediction of stable crystal structures under different pressure conditions based solely on chemical composition, and has become a key theoretical approach for discovering novel high-pressure phases and understanding matter under extreme condition. This review focuses on the global optimization problem on high-dimensional potential-energy and enthalpy landscapes under pressure constraints. We systematically review conventional crystal structure prediction methods, as well as recent applications of machine-learning interatomic potentials and crystal generative models to high-pressure CSP. Representative advances in theory-guided high-pressure materials discovery are further summarized across experimentally accessible and ultrahigh-pressure regimes, including high-temperature superconductivity in hydride compounds and boron-carbon systems, as well as materials relevant to the interiors of the Earth and ice giant planets. Finally, current challenges and future perspectives in high-pressure crystal structure prediction are discussed.