Reaction of Mg with the GaAs(001) surface occurs at substrate temperatures above 550 K and leads to three-dimensional (3D) growth of an epitaxial, cubic reaction phase with a lattice constant of 0.62 +/- 0.02 nm, 9% larger than GaAs. The resulting anisotropic, 3D heteroepitaxial microstructure was studied using in situ electron diffraction and Auger spectroscopy and ex situ atomic force microscopy (AFM). Three-dimensional structures develop that are elongated along the GaAs[110] direction with aspect ratios (length to width) up to 20. These structures appear to be composed of isotropic islands from which elongated, tapered ridges extend in one direction along [110]. Analysis of AFM images and size distributions suggest a critical size for the initiation of ridge growth. We speculate that these structures develop in response to misfit strain in the reaction phase.