В течение ледниковых периодов льды аккумулировали такое количество воды Мирового океана, что уровень моря на всей планете опускался на сотни футов ниже его современной отметки. В результате участки земной поверхности, которые сегодня заняты мелководными морями, разделяющими Юго-Восточную Азию и индонезийские острова Суматра, Борнео, Ява и Бали, превращались в участки суши. (То же самое происходило и с другими мелководными участками, такими как Берингов пролив и Ла-Манш.) Материковая окраина Юго-Восточной Азии тогда находилась на 700 миль восточнее ее нынешнего положения. Тем не менее острова Центральной Индонезии между Бали и Австралией были окружены и отделены от Австралии глубоководными проливами. Жителям материка, чтобы достигнуть Австралии/Новой Гвинеи, в то время требовалось пересечь самое меньшее восемь таких проливов, самый большой из которых имел минимум 50 миль в ширину. Чаще всего острова, разделенные проливами, были не видны друг с друга, однако сама Австралия оставалась вне видимости даже с самых ближайших индонезийских островов, Тимора и Танимбара. Таким образом, колонизация Австралии/Новой Гвинеи стала серьезной исторической вехой, поскольку не могла состояться без морских судов, и до сих пор является самым ранним свидетельством их применения. Только тридцать тысяч лет спустя (13 тысяч лет назад) появляются следующие бесспорные свидетельства существования мореходства — на этот раз в регионе Средиземноморья.
Первоначально археологи рассматривали возможность непреднамеренного заселения Австралии/Новой Гвинеи — горстка рыболовов, находившихся на плоту вблизи берега какого-нибудь индонезийского острова, могла быть отнесена в море. Экстремальный сценарий предполагает, что первых колонистов могло быть только двое: беременная женщина и плод мужского пола у нее в утробе. Однако совсем недавно сторонников теории случайной колонизации ждал сюрприз: выяснилось, что острова, лежащие к востоку от Новой Гвинеи, были заселены вскоре после самой Новой Гвинеи — примерно 35 тысяч лет назад. Это были Новая Британия и Новая Ирландия, острова архипелага Бисмарка, и Бука, относящийся к Соломоновым островам. Бука не виден с ближайшего острова к западу от него, и чтобы попасть сюда, нужно было преодолеть минимум 100 миль по воде. Стало быть, у первых австралийцев и новогвинейцев, скорее всего, были средства, чтобы целенаправленно достигать видимых островов, и они пользовались судами достаточно часто, чтобы колонизация даже невидимых островов, несмотря на непреднамеренность, не была единичным случаем.
Заселение Австралии/Новой Гвинеи возможно было связано с еще одним из первых событий (помимо первого использования морских судов и первого расширения ареала человека после колонизации Евразии): первым массовым истреблением людьми крупных видов животных. Сегодня, представляя себе континент, где водятся крупные млекопитающие, мы по умолчанию думаем об Африке. Многие виды крупных млекопитающих обитают и в современной Евразии (пусть и не в таком изобилии, как на территории африканских саванн Серенгети) — это азиатские носороги, слоны и тигры, европейские лоси, медведи, а также (до классической эпохи) львы. В Австралии и на Новой Гвинее сопоставимых по размеру млекопитающих не существует — здесь нет никого крупнее 100-фунтовых кенгуру. А ведь в свое время общий для них праматерик обладал собственным набором крупных зверей, включая гигантских кенгуру, носорогоподобных сумчатых (дипродонтов), достигавших размера коровы, и сумчатого «леопарда». Его также населяли 400-фунтовые нелетающие птицы, похожие на страусов, плюс несколько громадных рептилий, в том числе ящер весом в тонну, гигантский питон и сухопутные крокодилы.
Все эти австралийские/новогвинейские гиганты (так называемая мегафауна) исчезли после появления людей. Хотя в вопросе о точном времени их исчезновения нет единодушия, тщательное изучение материалов нескольких австралийских раскопок, где возраст ископаемых достигает десятков тысяч лет и где содержатся огромные залежи костных остатков животных, не выявило ни единого следа вымерших гигантов за последние тридцать пять тысяч лет. Следовательно, наиболее вероятно, что мегафауна перестала существовать на континенте вскоре после того, как сюда добрались люди.