A recent paper in PNAS uses ancient DNA research to determine when bison first "invaded" North and South America. The iconic symbols of the N. American west haven't actually been here that long. It turns out that the first migration of bison from Asia occurred between 195 and 135 thousand years ago. Here is a shorter report on the research from The New York Times.