Solving the crystal structures of novel phases with nanoscale dimensions resulting from rapid quenching is difficult due to disorder and competing polymorphic phases. Advances in computer speed and algorithm sophistication have now made it feasible to predict the crystal structure of an unknown phase without any assumptions on the Bravais lattice type, atom basis, or unit cell dimensions, providing a novel approach to aid experiments in exploring complex materials with nanoscale grains. This approach is demonstrated by solving a long-standing puzzle in the complex crystal structures of the orthorhombic, rhombohedral, and hexagonal polymorphs close to the Zr2Co11 intermetallic compound. From our calculations, we identified the hard magnetic phase and the origin of high coercivity in this compound, thus guiding further development of these materials for use as high performance permanent magnets without rare-earth elements.