Scanning tunneling microscopy and low energy electron diffraction have been used to study the alpha-Fe2O3(0001) surface in an ultrahigh vacuum. Our results show that this surface can be stabilized by coexisting alpha-Fe2O3(0001) and FeO(111) phases, with each phase existing in atomically well-ordered islands of mesoscopic dimensions. Furthermore, the islands themselves are arranged to form a superlattice. The formation of this superlattice can be explained in terms of the lattice mismatch between two types of oxygen sublattices.