Increasing the Al concentration in Al-doped ZnO (AZO) is one way of improving the conductivity of this transparent conductive oxide (TCO). Beyond a certain concentration, an unwanted secondary phase develops with a low conductivity. Its stoichiometry is Zn3Al2O6, and its crystal structure has not yet been convincingly determined. By applying unbiased ab initio structure prediction tools, we predict the crystal structure of Zn3Al2O6 to be monoclinic with space group Pm. It can be described as a nanofabric, with one-dimensional Al2O3 wires penetrating a ZnO matrix. This crystal has a formation energy that is lower than any structure proposed before, and is consistent with all available experimental information. Knowledge of the nature of this phase can help to avoid its formation and therefore to engineer AZO crystals with an increased level of Al-doping and associated increased conductivity.