I've found it surprisingly hard to find an answer to this question.
Niue is an uplifted coral reef jutting above the ocean. The rock is all limestone, and there is evidence for it being around for considerable time. There are many places where you can find caves that are exposed to air, and the formations inside those caves, while smoothed with time and exposure to the elements, are nonetheless impressive (Talava Arches and Avaiki cave are a couple of examples). The size of these formations suggests they were underground (but above water) for at least several hundred thousand years before becoming exposed to the outside world.
That's as far as I've got. Various histories of the Island I've read always seem to start with colonisation in 900 AD.