Since 2002 the VHE (>100 GeV) gamma-ray flux of the high-frequency peaked BL Lac PKS 2155-304 has been monitored with the High Energy Stereoscopic System (HESS). An extreme gamma-ray outburst was detected in the early hours of July 28, 2006 (MJD 53944). The average flux above 200 GeV observed during this outburst is ~7 times the flux observed from the Crab Nebula above the same threshold. Peak fluxes are measured with one-minute time scale resolution at more than twice this average value. Variability is seen up to ~600 s in the Fourier power spectrum, and well-resolved bursts varying on time scales of ~200 seconds are observed. There are no strong indications for spectral variability within the data. Assuming the emission region has a size comparable to the Schwarzschild radius of a ~10^9 solar mass black hole, Doppler factors greater than 100 are required to accommodate the observed variability time scales.