We have developed an efficient and reliable methodology for crystal structure prediction, merging ab initio total-energy calculations and a specifically devised evolutionary algorithm. This method allows one to predict the most stable crystal structure and a number of low-energy metastable structures for a given compound at any P-T conditions without requiring any experimental input. Extremely high (nearly 100%) success rate has been observed in a few tens of tests done so far, including ionic, covalent, metallic, and molecular structures with up to 40 atoms in the unit cell. We have been able to resolve some important problems in high-pressure crystallography and report a number of new high-pressure crystal structures (stable phases: ε-oxygen, new phase of sulphur, new metastable phases of carbon, sulphur and nitrogen, stable and metastable phases of CaCO3). Physical reasons for the success of this methodology are discussed.