En 1629, un vaisseau hollandais nommé Batavia et commandé par le capitaine Plessart ayant été séparé de la flotte des Indes par la tempête, vint faire naufrage sur les côtes de cette terre dont il fit la première découverte. Plessart ayant fait passer un petit bateau couvert à l'île de Java, située à 200 lieues au nord de cet endroit. La compagnie hollandaise qui est dans cette île lui ayant donné un vaisseau, il revint trouver les gens de son équipage qu'il avait laissés dans l'endroit où le vaisseau avait échoué.
Ils virent dans ce pays des hommes nus qui portaient de longs bâtons et il y en avait une partie qui marchait à quatre pattes comme des bêtes. Ces sauvages se laissèrent approcher des Hollandais jusqu'à la portée du fusil, après cela, ceux qui marchaient à quatre pattes se redressèrent et ils s'enfuirent tous. Quelques temps après en 1644, d'autres Hollandais ayant fait la découverte de plusieurs côtes de cette terre la nommèrent Nouvelle-Hollande. Guillaume Dampier, anglais, en faisant le tour de la terre, aborda dans la Nouvelle-Hollande en 1688. Voici un extrait de ce qu'il en dit : ces peuples sont tous des plus sauvages et mènent une vie très misérable, ils sont grands, droits et menus, de couleur brune, fort laids de visage n'ont point de barbe et ont des cheveux crépus comme les nègres. Ils portent pour tout habillement une ceinture d'écorce d'arbre. Ils ne font point de cabanes, mais couchent par terre comme des brutes et sans se couvrir. Il n'y a point d'arbres fruitiers dans leur pays, les autres arbres même y sont assez rares et ont le tronc fort menu. On n'y voit point d'animaux, excepté des oiseaux qui sont gros comme des merles.
La mer qui baigne ces côtes est peu poissonneuse, ces peuples font des trous sur le rivage où le flux laisse quelques petits poissons qui sont leur principale nourriture. Ils mangent aussi des moules et des limaçons. Comme ces sauvages n'ont que de mauvaises armes, et sont fort maladroits, ils ne peuvent pas prendre les gros poissons, cependant ils savent parfaitement bien nager tant les hommes que les femmes, ce qui est cause qu'ils ne se servent point de canots pour aller dans les Indes, ni pour aucun autre usage.