As a result of heterosegregation, we have obtained a gallium nitride phase, including oriented micro- and nanocrystallites, on the surface of gallium arsenide. The mechanism underlying the growth of crystallites of the surface phase has been analyzed.