Gravitational waves are expected to be radiated by supermassive black hole binaries formed during galaxy mergers. A stochastic superposition of gravitational waves from all such binary systems would modulate the arrival times of pulses from radio pulsars. Using observations of millisecond pulsars obtained with the Parkes radio telescope, we constrained the characteristic amplitude of this background, Ac,yr, to be <1.0 × 10–15 with 95% confidence. This limit excludes predicted ranges for Ac,yr from current models with 91 to 99.7% probability. We conclude that binary evolution is either stalled or dramatically accelerated by galactic-center environments and that higher-cadence and shorter-wavelength observations would be more sensitive to gravitational waves.