No road trip is complete without a dog by your side, its head hanging out of the window to take in the sights and smells of your journey. That’s been true, in various forms, for at least 10,000 years, which is how long we humans have been traveling with our dogs by our sides. In fact, a recent study investigates the first occupation of New Zealand by turning away from the humans involved and instead examining their dogs: the canine passengers in the grand voyaging canoes of the ancient Polynesians.

Humans reached New Zealand – or Aotearoa, as it’s called by the Maori, the modern-day descendants of the first settlers – in the late 1200s CE, making it the last major landmass on Earth to be settled. (Antarctica, of course, still has no indigenous human inhabitants.) Reaching New Zealand was the final step in a process that began over 60,000 years ago, when Homo sapiens first left Africa, and required the development of advanced navigation and seafaring technologies to cross the immense barrier of the Pacific Ocean. But humans didn’t come to New Zealand alone; they brought their dogs with them.

Outside of these few facts, archaeologists debate exactly how the settlement of New Zealand happened. For a long time, the dominant theory was that the first people arrived in a small group whose population slowly grew before they were eventually able to occupy the entire country. Lately, though, a different idea has gained support: that Polynesian explorers came in large numbers and dispersed rapidly, settling all of New Zealand within a century of their arrival.

This second theory matches the Maori’s own oral history, the stories they tell of how and where they came from. To try and figure out which hypothesis is correct, archaeologists turned to everyone’s best friend: dogs. Specifically, they examined the DNA of the very first dogs to ever live on New Zealand.

Ancient DNA, often shortened to aDNA, is a rapidly growing field in archaeology. Although many of its most famous findings involve ancient human DNA, some historical questions are best answered by looking at the aDNA of plants and animals. For example, in the case of New Zealand, there are very few human burials from the earliest period of settlement. Dog bones are found in much larger numbers and at many more sites. Additionally, the scientific analysis of human remains raises ethical issues. The support of descendants should always be sought out, as some may not want to see their ancestor’s bones destroyed for the sake of the aDNA within, no matter how small of an amount of bone is required (these days it’s between 150 and 250 milligrams – about 1/20th of a teaspoon).

Earlier this year, archaeologist Karen Greig from the University of Otago, New Zealand, and her team looked into the aDNA of 27 dogs from four sites on New Zealand and one site on the nearby Cook Islands, all dated to between 1200 and 1400 CE. Unfortunately, only 23 of the dogs produced useable aDNA; the warm, wet environment of most of Polynesia quickly degrades DNA past the point of recovery. The team was able to compare their results to those of an earlier study, which had published the aDNA of 14 dogs from the single site of Wairau Bar. Wairau Bar was a large village on the coast of the South Island of New Zealand, and is dated to 1285-1300CE; the dogs found there probably belonged to the very first settlers, or at least are within a generation or two of them.

Greig and her team found that unlike the first humans on New Zealand (which past research suggests included at least 190 women and a larger number of men, a diverse community originating from multiple Polynesian islands working together), all 37 dogs were closely related. In fact, the two dogs tested from the Cook Islands showed more genetic diversity between them than did all 35 dogs from New Zealand. Two-thirds of the New Zealand dogs shared exactly the same haplotype (a set of markers usually inherited as a group from a parent), while most of the others differed by only one or two mutations. Additionally, the study found that there was no geographic patterning to the New Zealand dogs; dogs from two different sites were as likely to be related as two dogs from the same site. This discovery means that early New Zealand dogs were all descendants of a small group of very similar dogs, which were equally and quickly distributed around the whole country.

Perhaps this is what they should have expected to find. After all, the occupation of Polynesia involved moving from island to island; it’s only logical that each time humans explored a new land, they took along fewer dogs than the previous island. Over many generations, this would lead to a reduction in genetic diversity.

On the other hand, the first New Zealanders may have deliberately chosen to bring only a few dogs along. When Maori and Europeans first came into contact in the 1790s, dogs were highly valued on New Zealand. They worked as guards and hunters and were also beloved companions. After death, dogs were sometimes eaten in special ceremonies, and their bones became the raw material for tools like fish hooks and items of jewelry. The most valuable dogs were used to make dogskin cloaks, a precious belonging meant only for people of chiefly status. White dogs with long-haired tails were particularly prized for this purpose. And to consistently create dogs with a specific look, it would be necessary to mate together those who had the right traits, just like dog breeders do today. Purebred dogs have much less genetic diversity than mutts do, because selecting for the same trait over and over shrinks the gene pool.

Five hundred years before Europeans made the first written records of Maori preferring white dogs with tassel-like tails, perhaps early Polynesians were already using practices that would create such a breed. We can’t be sure this explanation is why we see so little genetic diversity in the first New Zealand dogs, but the aDNA evidence suggests that it’s a possibility.

Greig and her team’s study of dog aDNA complements earlier studies of aDNA from humans and Pacific rats (Rattus exulans), along with other studies that investigated more traditional archaeological materials like stone tools and pottery. By combining these many approaches, we now have a more accurate, more complete picture of the first occupation of New Zealand: the people came in large numbers from a widespread zone of islands, but the dogs they brought with them were fewer in number and perhaps specially chosen.

Once on New Zealand, people, their dogs, and rats (most likely unwanted stowaways) all spread out quickly, covering both islands of the country from the coast to the highlands within 100 years of arrival. The people discovered new resources like high-quality obsidian and adapted to hunting local animals like fur seals and the now-extinct moa. Nonetheless they kept in close contact with one another and with their former homeland, which we can trace by the movement of trade goods – a category that included dogs.

Although much remains to be learned about the first occupation of New Zealand and the rest of Polynesia, Greig’s study of aDNA from dogs has helped to clarify our understanding of this important moment in human history. Next time you bring your dog along on a trip, think about the clues you’re both leaving behind for future archaeologists. It may be more than you think.