We propose a methodology for crystal structure prediction that is based on the evolutionary algorithm USPEX and the machine-learning interatomic potentials actively learning on-the-fly. Our methodology allows for an automated construction of an interatomic interaction model from scratch, replacing the expensive density functional theory (DFT) and giving a speedup of several orders of magnitude. Predicted low-energy structures are then tested on DFT, ensuring that our machine-learning model does not introduce any prediction error. We tested our methodology on prediction of crystal structures of carbon, high-pressure phases of sodium, and boron allotropes, including those that have more than 100 atoms in the primitive cell. All the the main allotropes have been reproduced, and a hitherto unknown 54-atom structure of boron has been predicted with very modest computational effort.