However, before we get back that far in evolutionary history we discover that, for much of the Age of Mammals, there was an additional family of animals belonging to the broad group that includes both bears and dogs, and which is no longer with us. These were the beardogs, more technically known as amphicyonids.
Beardogs were not, despite the name, the ancestors of bears and dogs. They were a separate family, one containing animals that looked a bit like bears and a bit like dogs, and which needed a common name of their own. "Beardogs" gets across both those physical features and the fact that they are, indeed, related to the two living families... having said which, it is not at all clear which, if either, of the two they are closer to, in part because the first of them appeared so early.
(Beardogs should not, of course, be confused with dog-bears, another family, or perhaps subfamily, of extinct animals that were much closer to actual bears, and lived at about the same time. But who'd do that, eh?)
Beardogs were widespread, inhabiting, at one point or another, all of the continents of the Northern Hemisphere. A great many species have been identified, and, as always, there are doubtless more we have yet to uncover. The oldest forms known were relatively small, and tended to be more "dog-like", while the later, larger, forms, had more ursine features. For example, many of the larger species walked on the soles of their feet, as bears do, rather than using the more tip-toe stance typical of dogs (and of their own ancestors).
The best known beardog is almost certainly Amphicyon, from which the group takes its scientific name. It was a large animal, and widely distributed itself, but it may have been outlasted by the less well known Cynelos. This is, of course, like Amphicyon, a genus, or group of very closely related species, rather than a single species in its own right. It's as if we were describing black, brown, and polar bears as all being the same thing (Ursus, in that case)... but when all you have is skeletons, most of them incomplete, there is an advantage to that sort of shorthand.
Nonetheless, several species of Cynelos have been named, many of them on fairly fragmentary evidence. They were first described on the basis of fossils discovered in Auvergne, France in the early 1860s, but have since been found much further afield. Even so, Europe appears to be where they first appeared, since the very oldest Cynelos fossils we know of come from Quercy, which is only a little further south. Those fossils date to about 25 million years ago, and it was presumably after that that these beardogs began to spread out across the globe.
What route did they take to do this? Perhaps they started by heading into Asia, but we have few good fossil deposits of the right age to have found much evidence of this. Certainly, some fragments from Miocene Asia have been assigned to Cynelos, but it's probably fair to say that the details remain unclear. We know, however, that they entered Africa, and probably did so quite early on, with fossils known from as far south as Uganda and Kenya. Indeed, it seems to be here that these particular bear dogs made their last stand, dying out around 5 million years ago, towards the end of the Miocene, a few million years after they had died out elsewhere in the world.
What's more surprising is that Cynelos is also known from North America, and may well even have gotten there before it reached Africa. The earliest fossils come from Nebraska, and have been dated at 23 million years old, just a couple of million years after the oldest fossils in Europe, and lining up with the very beginning of the Miocene epoch, from which most beardog fossils are known. From Nebraska, these early beardogs spread out across the continent. It was to be another four million years before they were joined by the more famous, and larger, Amphicyon, which also headed across from Asia.
It had been thought that Cynelos reached the Atlantic and Gulf of Mexico regions of North America long before it reached what is now the western contiguous US. Recently, however, during excavation to rebuild State Route 241 in California, rock was exposed that turned out to contain, among other things, the skull of a beardog much older than anything previously found in that corner of the continent. Researchers identified it as belonging to the species Cynelos malasi, and, while its exact age is uncertain, a best guess seems to be in the general vicinity of 21 million years old.
The skull belonged to a relatively small beardog, and has the typical long, rather dog-like snout of the animals, and, so far as we can tell without the rest of skeleton, probably belonged to something closer in size to a dog than a bear - and not a particularly large dog, at that. Indeed, aside from a dwarf species found in Florida, it's one of the smallest beardogs found in North America. This would fit with it being early, with the larger, more bear-like forms only evolving later, and many of them likely direct descendants of this animal. (As is common, though, it's hard to say which ones, or what the exact sequence was).
Since beardogs must surely have entered North America by crossing over the Bering Straits from Asia, that they quite quickly sauntered down the Pacific coast, rather than simply heading straight inland to Nebraska, makes a lot of sense. Quite how they got to the Bering Straits in the first place, though, is less clear. The obvious explanation is that they just went across Siberia, travelling from northeastern Europe. But, given the fossils we have, it's just as likely that they took a southern route, perhaps heading to Africa first, then back into southwestern Asia, and round through China.
Either way, it can't have been an easy trip. Sure, they had a couple of million years to make it, so speed of travel was hardly an issue. But they would have had to cross through a wide range of different climates and terrains on the journey. "Brief" period of climate change, on the order of hundreds of thousands of years, may have helped a little, letting them move a little bit further each time, but, even so, it's likely that they must have been quite adaptable animals.
But, then, they were carnivores, and, with one of their more dog-like features being the shape of their skull, they probably ate more meat than modern bears do. So long as they didn't care too much where that meat came from, and so long as they avoided the steep mountains where their short legs would have put them at a disadvantage, varied terrain may not have been too much of a problem.
Which might explain why such similar animals are found from France to Florida.
[Photo by "Ghedoghedo", from Wikimedia Commons]