In contrast to the seasonal, predictable migrations of birds in Europe and North America the nomadic waterbirds of the arid interior of Australia must travel large distances to locate seasonally and spatially unpredictable water resources which are ephemeral. How Australian waterbirds have adapted their behaviour to this desert environment and are able to locate ephemeral water bodies in this vast landscape is a major unsolved puzzle of bird migration. During La Niña conditions, which caused heavy rainfall and an influx of waterbirds into the interior, we deployed a large number of satellite transmitters on the iconic Australian black swan (Cygnus atratus). Tracked individuals were successful in locating new ephemeral water across hundreds of kilometres. Individuals usually moved at night and we found several weather variables predicted the timing of their movements, such as temperature. With conditions in the interior deteriorating for waterbirds after the La Niña period ended, birds moved to coastal and inland refugia although these two strategies came at different costs to individuals. Our findings provide new insight into connectedness of waterbird habitat in Australia, the navigational capabilities of nomadic species and how Australian waterbirds have adapted to an environment which can rapidly change.