Gallium nitride (GaN) nanostructures were fabricated by focused-ion-beam-assisted chemical vapor deposition. Gallium precursor gas and atomic nitrogen radicals were irradiated onto the surface simultaneously during the irradiation of a Ga ion beam of 25keV at 600°C. Scanning electron microscopy observations revealed three-dimensional structures formed periodically on the substrates. Although near-band-edge emission from GaN was observed using this method, other luminescence attributed to defects and/or impurities was also observed. Surface damage caused by the ion beam was also observed. To improve the structural shape and optical properties, a two-step growth method is proposed. First, structure formation was performed at 300°C. Second, nitridation was performed at 600°C to make the GaN nanostructures stoichiometric and to activate the nitrogen in the structures. GaN nanostructures of a 200nm×100nm block of height 50nm were fabricated and strong near-band-edge emission at 3.37eV from GaN was observed.