We demonstrate vertically aligned epitaxial GaAs nanowires of excellent crystallographic quality and optimal shape, grown by Au nanoparticle-catalyzed metalorganic chemical vapor deposition. This is achieved by a two-temperature growth procedure, consisting of a brief initial high-temperature growth step followed by prolonged growth at a lower temperature. The initial high-temperature step is essential for obtaining straight, vertically aligned epitaxial nanowires on the (111)B GaAs substrate. The lower temperature employed for subsequent growth imparts superior nanowire morphology and crystallographic quality by minimizing radial growth and eliminating twinning defects. Photoluminescence measurements confirm the excellent optical quality of these two-temperature grown nanowires. Two mechanisms are proposed to explain the success of this two-temperature growth process, one involving Au nanoparticle-GaAs interface conditions and the other involving melting-solidification temperature hysteresis of the Au-Ga nanoparticle alloy.