We report on the growth of AlxGa1-xN nanowires by plasma-assisted molecular beam epitaxy for x in the 0.3-0.8 range. Based on a combination of macro- and micro-photoluminescence, Raman spectroscopy, x-ray diffraction and scanning electron microscopy experiments, it is shown that the structural and optical properties of AlGaN NWs are governed by the presence of compositional fluctuations associated with strongly localized electronic states. A growth model is proposed, which suggests that, depending on growth temperature and metal adatom density, macroscopic composition fluctuations are mostly of kinetic origin and are directly related to the nucleation of the AlGaN nanowire section on top of the GaN nanowire base which is used as a substrate.