Recent claims for continent wide disappearance of megafauna at 46.5 thousand calendar years ago (ka) in Australia have been used to support a “blitzkrieg” model, which explains extinctions as the result of rapid overkill by human colonizers. A number of key sites with megafauna remains that significantly postdate 46.5 ka have been excluded from consideration because of questions regarding their stratigraphic integrity. Of these sites, Cuddie Springs is the only locality in Australia where megafauna and cultural remains are found together in sequential stratigraphic horizons, dated from 36-30 ka. Verifying the stratigraphic associations found here would effectively refute the rapid-overkill model and necessitate reconsideration of the regional impacts of global climatic change on megafauna and humans in the lead up to the last glacial maximum. Here, we present geochemical evidence that demonstrates the coexistence of humans and now-extinct megafaunal species on the Australian continent for a minimum of 15 ka.