The usage of a BexZn1-xO alloy in ultraviolet (UV)-region optoelectronic devices is largely hindered by its intricate phase segregation of crystallites of different sizes. To understand the physical origin of this phase segregation phenomenon on the atomistic scale, we have undertaken an extensive study of the structural evolution of the segregation phases in the BexZn1-xO alloy at finite temperatures by using first-principles calculations combined with the cluster expansion approach. We find that a random alloy of BexZn1-xO tends to segregate into a mix-ordered phase below a critical temperature, by the growth of prototype and nano-sized structures. The segregated phases in BexZn1-xO entail not only ZnO or BeO crystallites, but also two as yet unreported phases with beryllium concentration of 1/3 and 2/3. Both new phases of BexZn1-xO are direct wide-gap semiconductors with band gap values of 4.88 eV and 6.78 eV respectively. We envisioned that the novel Be1/3Zn2/3O crystal is highly promising for solar-blind device applications.