The timing, context and nature of the first people to enter Sahul is still poorly understood owing to a fragmented archaeological record. However, quantifying the plausible demographic context of this founding population is essential to determine how and why the initial peopling of Sahul occurred. We developed a stochastic, age-structured model using demographic rates from hunter-gatherer societies, and relative carrying capacity hindcasted with LOVECLIM’s net primary productivity for northern Sahul. We projected these populations to determine the resilience and minimum sizes required to avoid extinction. A census founding population of between 1,300 and 1,550 individuals was necessary to maintain a quasi-extinction threshold of ≲0.1. This minimum founding population could have arrived at a single point in time, or through multiple voyages of ≥130 people over ~700–900 years. This result shows that substantial population amalgamation in Sunda and Wallacea in Marine Isotope Stages 3–4 provided the conditions for the successful, large-scale and probably planned peopling of Sahul.