Low-temperature growth of AlxGa1-xAs by the solution - liquid-solid mechanism affords nanowhiskers having two specific overall compositions: x = 0.1 and 0.8. Intermediate compositions (0.1 < x < 0.8) are inaccessible by the method employed. Examination of the nanowhiskers by transmission electron microscopy, photoluminescence spectroscopy, electron energy loss spectroscopy, and annealing studies indicates that they possess compositionally modulated nanostructures. The observed compositional modulation consists of alternating comparatively Al-rich and Ga-rich AlxGa1-xAs domains with dimensions of 3-20 nm. The spontaneous phase separation, which occurs during growth, appears to be kinetically driven, and the resulting phase-separated nanostructures appear to be, therefore, metastable rather than stable. Spontaneous phase separation in AlxGa1-xAs, which strongly influences its photoemission behavior, is not well understood theoretically.