The Siberian Unicorn could have been alive some 29,000 years ago. Elasmotherium sibiricum was thought to have become extinct 350,000 years ago, but the discovery of a skull in the Pavlodar region of Kazakhstan suggests they were around till fairly recently.
The Harappan Unicorn was of course around much more recently (less than 10,000 years ago).
Big animals, living in small groups rather than in a herd, not very aggressive, and herbivorous rather than carnivorous with the single horn as their defense against predators?
A furry unicorn for Siberia and a summer-adapted, tame one for the Indus-Saraswati Valley?