DNA fragments are known from bone fragments from the Mesozoic, but these don't count. I'm guessing the oldest DNA is recovered from permafrost, but how old exactly?
Well, the oldest intact DNA found is actually 419 million years old, and it belongs to (not surprisingly) bacteria. Samples were extracted from surface-sterilized salt of different geological ages (23, 121, 419 million years of age, MYA).
But as you mentioned, these are fragments. Studies on the half-life of DNA suggest that even under ideal circumstances, DNA sequences older than 1.5 million years will be too short to be readable.
The oldest genome known to date, though, is 700,000 years old, and was recovered from samples from a horse leg bone. You were correct, the leg was in permafrost. That's a considerable jump from mastodon and polar bear fossils which were about 50,000 and 110,000 years old.