The analysis of Coulomb crystallization is extended from one-component to two-component plasmas. Critical parameters for the existence of Coulomb crystals are derived for both classical and quantum crystals. In the latter case, a critical mass ratio of the two charged components is found which is of the order of 80. Thus, holes in semiconductors with sufficiently flat valence bands are predicted to spontaneously order into a regular lattice. Such hole crystals are intimately related to ion Coulomb crystals in white dwarf and neutron stars as well as to ion crystals produced in the laboratory. A unified phase diagram of two-component Coulomb crystals is presented and is verified by first-principle computer simulations.