Context. In arid and semi-arid river systems, waterholes are often the only refugia for aquatic organisms during no-flow spells. Sediment accumulation in waterholes reduces their persistence. Aims. To assess this threat, we surveyed the depth of, and dated, waterhole sediments from the Moonie River, a northern tributary of Australia's largest river system, the Murray-Darling Basin. Methods. Fine-sediment depth was determined in three of the deepest waterholes in 2010 and 2011 before, and after, the largest flood in over a century. The rate of sediment build up in two waterholes was also determined. Key results. In the deepest sections (>75th percentile depth), there was between 0.7 and 2 m of fine sediment in 2010. Following flooding, sediment depth reduced by 24-54%, with the largest proportional reductions in sediment occurring in the shallowest waterhole. However, net sediment accumulation is still 1.4-2.0 cm year(-1) since the 1950s. Conclusions. Sedimentation has reduced the persistence of the deepest waterholes by over 200 days, representing an up to 30% reduction. During the longest droughts known in the Moonie River, this would dry many otherwise permanent waterholes. Implications. Sedimentation is a marked threat to waterhole persistence even following large floods.