Robust regional seismic-hazard assessments require millennial-scale paleoseismic histories that extend far beyond the range of historical and instrumental data. However, it is difficult to resolve the probability density functions for earthquake recurrence from the limited number of major to great earthquakes most paleoseismic records contain. Lake sediment records are repositories of information about paleoearthquake recurrence, with a sensitivity and fidelity over millennial time scales that suggest that they have the potential to yield reliable estimates of the recurrence distribution. We present a 7000 yr paleoseismic record from Lake Tutira (North Island, New Zealand) that ranks among the most detailed Holocene paleoearthquake chronologies available worldwide, and use it to empirically constrain the recurrence distribution of earthquakes with a minimum ground-shaking intensity of MMI 7 in one of New Zealand's most seismically active areas. Our analysis confirms that a Poisson process describes the waiting times of single moderate to major and/or great paleoearthquakes in the Hawke's Bay region.