Researchers used radiocarbon dating to determine the ages of 28 of the animals, and estimated that one female was about 400 years old.
The team found that the sharks grow at just 1cm a year, and reach sexual maturity at about the age of 150.
The research is published in the journal Science.
[caption id="attachment_9933" align="aligncenter" width="624"]
A shark seen near Disko Bay in western Greenland. Photo: Julius Nielsen[/caption]
Lead author Julius Nielsen, a marine biologist from the University of Copenhagen, said: "We had our expectations that we were dealing with an unusual animal, but I think everyone doing this research was very surprised to learn the sharks were as old as they were."
The former vertebrate record-holder was a bowhead whale estimated to be 211 years old.
But if invertebrates are brought into the longevity competition, a 507-year-old clam called Ming holds the title of most aged animal.
Greenland sharks are huge beasts, that can grow up to 5m in length.
They can be found, swimming slowly, throughout the cold, deep waters of the North Atlantic.
With this leisurely pace of life and sluggish growth rate, the sharks were thought to live for a long time. But until now, determining any ages was difficult.
For some fish, scientists are able to examine ear bones called otoliths, which when sectioned, show a pattern of concentric rings that scientists can count as they would the rings in a tree.
Sharks are harder, but some species, such as the Great White, have calcified tissue that grows in layers on their back bones, that can also be used to age the animals.
[caption id="attachment_9935" align="aligncenter" width="624"]
A Greenland shark after its release from the research ship. Photo: Julius Nielsen[/caption]
"But the Greenland shark is a very, very soft shark - it has no hard body parts where growth layers are deposited. So it was believed that the age could not be investigated," Mr Nielsen told the BBC.
However the team found a clever way of working out the age.
"The Greenland shark's eye lens is composed of a specialised material - and it contains proteins that are metabolically inert," explained Mr Neilson.
"Which means after the proteins have been synthesised in the body, they are not renewed any more. So we can isolate the tissue that formed when the shark was a pup, and do radiocarbon dating."
The team looked at 28 sharks, most of which had died after being caught in fishing nets as by-catch.
[caption id="attachment_9936" align="aligncenter" width="624"]
A Greenland shark caught as by-catch. Photo: Julius Nielsen[/caption]
Using this technique, they established that the largest shark - a 5m-long female - was extremely ancient.
Because radiocarbon dating does not produce exact dates, they believe that she could have been as "young" as 272 or as old as 512. But she was most likely somewhere in the middle, so about 400 years old.
It means she was born between the years of 1501 and 1744, but her most likely date of birth was in the 17th century.
"Even with the lowest part of this uncertainty, 272 years, even if that is the maximum age, it should still be considered the longest-living vertebrate," said Mr Nielsen.
Conversely, if her age is at the upper end of the scale, she will have out-lived Ming the clam - although her age has a greater probability of lying in the middle.
The team believes the animals only reach sexual maturity when they are 4m-long. And with this new, very lengthy age-range, it suggests this does not occur until the animals are about 150 years old.
The researchers say this has consequences for future conservation of the animals.
Because of their extreme longevity, Greenland sharks may still be recovering from being over-fished before WW2.
The sharks' livers were once used for machine oil, and they were killed in great numbers before a synthetic alternative was found and the demand fell.
[caption id="attachment_9937" align="aligncenter" width="624"]
Greenland sharks won't reach sexual maturity until they're 150. Photo: Julius Nielsen[/caption]
"When you evaluate the size distribution all over the North Atlantic, it is quite rare that you see sexually mature females, and quite rare that you find newborn pups or juveniles," Mr Nielsen explained.
"It seems most are sub-adults. That makes sense: if you have had this very high fishing pressure, all the old animals - they are not there any more. And there are not that many to give birth to new ones.
"There is, though, still a very large amount of 'teenagers', but it will take another 100 years for them to become sexually active."
Another author of the study, Prof Christopher Ramsey, director of Oxford Radiocarbon Accelerator
Unit at the University of Oxford, said that radiocarbon dating could be used to determine the ages of other animals, but was not likely to be chosen as the primary method.
"For many animals we have other methods to determine age," he said.
"Also, the radiocarbon method is not very precise, and so is only really relevant for very long-lived species."
He added that the statistical method used to determine the sharks' ages was Bayesian statistics.
"Bayesian statistics were first worked out by the Rev Bayes in the 18th Century. This means he will have been working on this when some of these oldest sharks were young."