It shows that the mammoth was most closely related to the Asian rather than the African elephant.
The three groups split from a common ancestor about six million years ago, with Asian elephants and mammoths diverging about half a million years later.
"We have finally resolved the phylogeny of the mammoth which has been controversial for the last 10 years," lead author Michael Hofreiter of the Max Planck Institute for Evolutionary Anthropology in Leipzig, Germany, told the BBC News website.
The DNA of several extinct ice age mammals, preserved in permafrost, has been analysed before, but not in such detail.
"It is the longest stretch of DNA [decoded to date] from any Pleistocene species," said Professor Hofreiter.
The team of researchers - from Germany, the UK, and the US - extracted and analysed mammoth DNA using a new technique that works on even the tiny quantities of fossilised bone - in this case 200 milligrams.
Some 46 chunks of DNA sequence were matched up and arranged in order, giving a complete record of the mammoth's mitochondrial DNA - the circular scrap of genetic material found outside the cell's nucleus.
A write up of the research will appear in Nature Online...