The traditional view of New Zealand fauna is that its wide range of unique bird life flourished due to the absence of mammals to prey on or compete against them. That is, until the arrival of humans (who also brought rats and dogs) around a thousand years ago.
In fact, there are at least three species of native mammals - but they are excluded in the above narrative - bats, seals and sealions.
taking a long step back, New Zealand was once part of the great southern land, Gondwana, finally separating around 85 million years ago (see Wikipedia and University of Waikato) - the former indicates New Zealand separated specifically from the Antarctic land mass before Australia did; however, it's not clear whether Australia was at the time counted as Antarctica. It seems to me most likely that Australia was its last port of call, since the coastlines match so neatly.
In 2006, a mouse-sized mammalian fossil 16 to 19 million years old was discovered in New Zealand's St Bathans fossil bed, in the south of the South Island. This has been written up in PNAS (Proceedings of the National Academy of Sciences [of the USA], available here. Interestingly, in the paper it is said to be "nontherian". That is, it split from the mammal lineage before marsupials: therians are defined as non-egglaying mammals: thus this one (the 'SB mammal') would be defined as an egglayer.
Colin Tudge's 2000 book The Variety of Life details the metatherians (marsupials) and eutherians (so-called placentals), then mentions eight groups of nontherians, of which only the monotremes (Australia's platypus and echidna) survive; of the others, only multituberculates and morganucodonts are mentioned. Wikipedia has an entry on Prototherians (aka non-therians), but Tudge doesn't recognise this as a clade, only as a small-p colloquial term for a non-therian mammal. Wikipedia adds to the group Triconodonta and Docodonta; as you can see, the classifications are mainly based on tooth characteristics. Why? Tudge: "Most of the extinct lineages are known only from a few teeth and jaws" - prescient, as this is also the case for the SB mammal, with the addition of a bit of hip. (Braincase is also mentioned as a differentiating characteristic.) I've seen no word on the placement of this creature within non-therians (Wikipedia's entry says the SB mammal is not a monotreme) - probably not an easy task, and the discovery's only about a year old.
I remain curious, too, about the other three of Tudge's non-therian clades; however, Tudge constantly reminds us that at this level of taxonomy, judgment calls are inevitably involved.
Eutherians ('placentals') and marsupials split 100 to 125 million years ago; this specimen dates from 16 to 19 million years (see the entry in New Scientist), suggesting this creature survived for at least 100 million years. Notably, this is the first land mammal fossil found in New Zealand.
The ubiquitous Mike Archer, current UNSW Science Dean, was involved in this study. He suggests it goes against the conventional wisdom that New Zealand temporarily disappeared below the water from 25 to 30 million years ago [due to some combination of rising oceans and/or erosion] after separation from Gondwana, and re-emerged due to its location on the boundary of two techtonic plates pushing against each other. Archer reckons it was too small to succeed at rafting [so it must have remained indigenous since before the split; others disagree.
So, did New Zealand stay above water, or did the SB mammal raft?
I'm currently reading Richard Dawkins' The Ancestor's Tale (2004, Phoenix, London), and he is a great believer in the ability of rafting to explain movements. In a nutshell, rafting is the drift of land-based animals on floating vegetation masses, typically due to the effects of storms. Dawkins (p150) details a large-scale eyewitness event (iguanas in the Carribean) and makes the case that, although this may call for highly improbable events, over a long enough period of time these can come to pass.
However, New Zealand's submergence (as well as erosive forces - see the U Waikato link) does explain the lack of landbased fossils.
What then, of the Tuatara? When I was growing up, the Tuatara was represented on the five cent piece, and typified as a rare lizard - preserved due to isolation on several island just off New Zealand's mainlands. They are actually uniquely-surviving lizard-like Sphenodontians, creatures that flourished 200 million years ago. Further, they show unique cold-climate adaptions over the original warm-climate sphenodontians. That's not unexpected in the time that they've been isolated, but it suggests they were in New Zealand when it was in a warmer climate. It seems to me less likely than that they rafted as recently as 25 million years ago, subsequently disappearing in their home location.
Neither explanation is fully satisfactory. On the one hand, New Zealand entirely lost its land-based fauna. On the other hand, two uniquely survived - at least until recently, and certainly after New Zealand's purported submergence.
It remains a puzzle for the moment.
Further discussion of this unusual find includes a number of reference links.