Betelgeuse, the bright, cool red supergiant in Orion, is moving supersonically relative to the local interstellar medium. The star emits a powerful stellar wind that collides with this medium, forming a cometary structure, a bow shock, pointing in the direction of motion. We present the first 3D hydrodynamic simulations of the formation and evolution of Betelgeuse's bow shock. The models include realistic low-temperature cooling and cover a range of plausible interstellar medium densities of 0.3-1.9cm–3 and stellar velocities of 28-73km/s. We show that the flow dynamics and morphology of the bow shock differ substantially because of the growth of Rayleigh-Taylor or Kelvin-Helmholtz instabilities. The former dominate the models with slow stellar velocities resulting in a clumpy bow shock substructure, whereas the latter produce a smoother, more layered substructure in the fast models. If the mass in the bow shock shell is low, as seems to be implied by the AKARI luminosities (∼3x10–3M☉), then Betelgeuse's bow shock is very young and is unlikely to have reached a steady state. The circular nature of the bow shock shell is consistent with this conclusion. Thus, our results suggest that Betelgeuse only entered the red supergiant phase recently.