We have prepared GaAs wurtzite (WZ)-zinc blende (ZB) nanowire heterostructures by Au particle-assisted metal-organic vapor phase epitaxy (MOVPE) growth. Superior crystal quality of both the transition region between WZ and ZB and of the individual segments themselves was found for WZ-ZB single heterostructures. Pure crystal phases were achieved and the ZB segments were found to be free of any stacking defects, whereas the WZ sections showed a maximum stacking fault density of 20 μm^-1. The hexagonal cross-sectional wires are terminated by {1010}-type side facets for the WZ segment and predominantly {110}-type side facets for the ZB part of the wire. A diameter increase occurred after the transition from WZ to ZB. Additionally, facets of the {111}-type as well as downwards-directed overgrowth of the WZ segments were formed at the WZ to ZB transition to compensate for the observed diameter increase and facet rotation. In the case of WZ-ZB multiple heterostructures, we observed slightly higher densities of stacking faults and twin planes compared to single heterostructures.