Арабские купцы и мореплаватели в начале новой эры основали колонию на западном берегу Суматры и с того времени осуществляли оживленную торговлю.
К приходу европейцев в Юго-Восточную Азию в XVI веке Китай имел уже более чем полуторатысячелетнюю историю связей с народами этого района. Его корабли сотни лет курсировали в Индийском океане. Однако никто из мореплавателей не рискнул пойти на юг от Явы или Тимора. Никто не знал, что там находится, но и недостатка в фантастических рассказах о тех краях не было.
Так, индийцы, жившие на Яве, Суматре и других островах архипелага, утверждали, что южнее Явы и восточнее Тимора расположены острова, богатые золотом. Отсутствие каких-либо данных об их месторасположении компенсировалось подробнейшими описаниями городов с золотыми дворцами, окруженными роскошными садами, в которых мужчины наслаждаются обществом златокудрых женщин. Ступени лестниц, спускающихся от дворцов к прудам, усыпаны драгоценными камнями. Но наряду с красочными легендами о золотых островах из поколения в поколение передавалось страшное предупреждение о том, что каждый, кто попытается их достичь, погибнет. Рассказывали об огромном дереве, стоящем в море к югу от Явы, крона которого поднимается над водой. На ветвях дерева живет птица Гаруда, похожая на грифона; она летает по ночам и при этом носит в свое гнездо кого-нибудь из крупных животных, например слона, тигра или носорога.
В морях вокруг этих островов все течения имеют одно направление — к дереву, и корабли, попадающие в течения, оказываются у дерева и исчезают в бездне, а их команды становятся добычей Гаруды.
Легенды, подобные этой, так запугали яванцев, что они боялись удаляться на юг на сколько-нибудь значительное расстояние, а если течение несло их в том направлении, они бросали свои суда и на шлюпках добирались до берега.
Китайцы, хорошо изучив острова Юго-Восточной Азии, оставили немало описаний и легенд о землях к югу, не предприняв никаких попыток их исследовать. Арабские описания земель, находящихся к югу и юго-востоку от Явы, не уступают индийским и китайским. Так, еще в XIII веке арабские мореплаватели рассказывали об острове «Уок-Уок», на котором растут деревья с плодами в виде человеческих черепов. Когда эти «плоды» созревают, из черепов раздается крик «Уок-Уок», и «плоды» падают на землю.
То ли из-за этих страшных рассказов, передававшихся из поколения в поколение на протяжении столетий, то ли просто из-за отсутствия необходимости, ни арабские, ни индийские, ни индонезийские, ни китайские мореходы не обнаружили берега Австралии. Это сделали европейцы.
В XV–XVI веках господство на морях и океанах земного шара захватили Португалия и Испания. Португальцы первыми из европейцев появились в Индийском океане. Васко да Гама в 1498 году достиг берегов Индии, в 1511 году Аффонсу Альбукерки захватил Малакку, и к концу того же года два португальских корабля под командой Антониу д’Абреу достигли Молуккских островов.
В отличие от своих азиатских предшественников португальцы были знакомы с идеей существования Terra Australia Incognita (Таинственной Южной Земли). В Европе эта идея возникла еще во времена античности. Конечно, это было чисто логическое рассуждение. Ни греки, ни римляне ничего не могли знать о существовании земли к югу от экватора, но считали, что массе суши на севере: Европе, Африке, Азии должна на юге противостоять не меньшая по размеру земля.
Живший в I веке нашей эры Помпоний Мела называл ее Землей антихтонов, а Птолемей спустя столетие — Неизвестной землей.
Но все античные авторы говорили о невозможности достичь этой земли и увидеть ее обитателей. Так, Помпоний Мела утверждал: «Об этих людях мы ничего не знаем, потому что между нами и ими находится огненная зона, пересечь которую невозможно».
Однако португальцам страшные рассказы о южных землях не помешали пересечь экватор и начать знакомиться с ними. В 1526 г. Жоржи ди Менезиш первым из европейцев ступил на остров Новая Гвинея.
Возможно допустить, что португальцы подходили к берегам Австралии или что-то о ней знали. Но никаких прямых свидетельств этому нет. Португальцы тщательно скрывали все сведения о географических открытиях своих мореходов. Невидимые миру, они лежали в лиссабонских архивах, которые почти все погибли во время страшного землетрясения 1755 года, разрушившего португальскую столицу.
Первое исторически зафиксированное европейское открытие Австралии было сделано голландским кораблем «Дейфкен»; он подошел к западному побережью полуострова Кейп-Йорк в марте 1606 года. На протяжении первой половины XVII века голландские суда неоднократно достигали западных и северных берегов пятого континента.
С конца XVII века господствующее положение в Южных морях переходит к Англии. В январе 1688 года У. Дампир достиг западных берегов Австралии, а в следующем году исследовал северо-западную часть континента. Наибольшее значение имело открытие Д. Куком восточного побережья Австралии в 1770 году. Спустя 18 лет после этого открытия и началась британская колонизация континента.