Whilst the precise dating of scarce remains and whether one can classify them as being from anatomically-modern humans are still subject to much debate, it has long been known that humans (ie homo sapiens) have been in Australia for a very long time. Archaic but anatomically-modern humans seem to arisen in west Africa around 200,000 years ago and then spread outwards through the Middle East and into Asia. To date the earliest remains of such humans in Australia are from about 60,000 years ago, which is roughly the same time, or indeed slightly earlier, than the earlist remains from humans in Europe north of the Mediterranean.
At this time extensive glaciation meant that sea levels were perhaps as much as 100m below the present level and accordingly land masses were more extensive, there were numerous 'land bridges' between the islands of the Indonesian archipelago, and New Guinea was joined to northern Australia. Nevertheless for humans to migrate from southern Asia down to Australia they still had to traverse extensive areas of open sea. The same climatic conditions, with extensive ice sheets covering much of Europe, probably accounts for why humans got from Africa to Australia before they got from Africa to Europe.
By contrast humans first arrived in New Zealand from Eastern Polynesia around 1300, ie just 700 years ago.