Although numerous crystal structures have been successfully predicted by using currently available computational techniques, prediction of strongly correlated systems such as transition-metal oxides remains a challenge. To overcome this problem, we have interfaced evolutionary algorithm-based USPEX method with the CRYSTAL code, enabling the use of Gaussian-type localized atomic basis sets and hybrid density functional (DFT) methods for the prediction of crystal structures. We report successful crystal structure predictions of several transition-metal oxides (NiO, CoO, α-Fe2O3, V2O3, and CuO) with correct atomic magnetic moments, spin configurations, and structures by using the USPEX method in combination with the CRYSTAL code and Perdew-Burke-Ernzerhof (PBE0) hybrid functional. Our benchmarking results demonstrate that USPEX + hybrid DFT is a suitable combination to reliably predict the magnetic structures of strongly correlated materials. Copyright © 2018 American Chemical Society.