The first peopling of Sahul (Australia, New Guinea and the Aru Islands joined at lower sea levels) by anatomically modern humans required multiple maritime crossings through Wallacea, with at least one approaching 100 km. Whether these crossings were accidental or intentional is unknown. Using coastal-viewshed analysis and ocean drift modelling combined with population projections, we show that the probability of randomly reaching Sahul by any route is <5% until ≥40 adults are ‘washed off’ an island at least once every 20 years. We then demonstrate that choosing a time of departure and making minimal headway (0.5 knots) toward a destination greatly increases the likelihood of arrival. While drift modelling demonstrates the existence of ‘bottleneck’ crossings on all routes, arrival via New Guinea is more likely than via northwestern Australia. We conclude that anatomically modern humans had the capacity to plan and make open-sea voyages lasting several days by at least 50,000 years ago.