Extreme precipitation events are one of the most consequential components of climate change for society. The El Niño-Southern Oscillation (ENSO) is the dominant mode of precipitation variability in the tropics and causes severe flooding and drought in many socioeconomically vulnerable regions. It remains unclear how tropical rainfall extremes and ENSO are changing in response to anthropogenic forcing, demanding that we investigate the relationships between precipitation, ENSO, and external forcing in the past. Lake sediment records have provided benchmark records of extreme flood events from the eastern tropical Pacific, where paleofloods have been interpreted to reflect El Niño events during the last millennium. However, the connections between flooding and ENSO variability in this region are uncertain, and the eastern Pacific can only capture precipitation events driven by El Niño, not La Niña. Thus, it is unclear how the ENSO system and tropical rainfall extremes have changed in the recent past. Here, we reconstruct flood events during the past millennium using a lake sediment record from East Java, Indonesia, which can provide insight into flooding driven by La Niña. We detect flood frequency variations in the western tropical Pacific that are highly coherent with records from the eastern part of the basin over the past millennium. Our findings demonstrate that heavy rainfall and flooding occurs more frequently on both sides of the tropical Pacific during periods of warmer Northern Hemisphere mean temperatures, implying that ENSO-driven rainfall extremes could intensify in the near future.