Structure prediction based on evolutionary/genetic algorithm methods combined with density functional theory calculations provides material scientists with a tool to predict from scratch the stable structure of a compound just with the mere knowledge of its composition. In practice, however, the process of accurate prediction of a new structure by simulations may be as time consuming as obtaining it in the lab. Here I will present some result of searching for new rare-earth free magnetic structures within the Horizon 2020 project NOVAMAG by using the evolutionary code USPEX and ab-initio code VASP. Based on this experience, I will bring into discussion the limitations as well as the possibilities for making the best use of structure predicting methods.