Mammoths first entered North America during the early Pleistocene, not long before the Ice Ages proper got going. They were, in their origin, Asian animals, but the mastodons were a different matter. Mastodons were already in North America when the mammoths arrived, and they had been there for a very long time indeed. For millions of years, America really was a place with herds of well... things that looked a lot like elephants, at any rate.
The creature that the American mammoths would have encountered was the American mastodon (Mammut americanum), an animal that first appeared close to the end of the Pliocene. But this was the last survivor of a much longer lineage, and there had been many more kinds of American proboscidean that lived before it, often alongside one another. In fact, only a minority of them were really mastodons, including the immediate predecessors of the American mastodon, such as Mammut raki, and the somewhat older Zygolophodon. The latter also lived in the Old World, and was likely the first mastodon to reach North America, shortly before the dawn of the Pliocene. Nonetheless, one of the best skulls we have of the animal was unearthed in California, and later mastodons of the continent are likely descended from something much like them.
But mastodons were not the only elephant-like creatures in America during the Pliocene. Just as, during the Pleistocene, they would share the continent with the mammoths, during the Pliocene they shared it with the gomphotheres. These animals had been in North America for even longer than the mastodons, and were a larger, and more varied, group. They were likely closer relatives of modern elephants than the mastodons were, although still different enough that we assign them to a different family.
Gomphotheres differed from true elephants in a number of features, among the most significant of which was that most of them had four tusks, rather than just the two. The second pair erupted from the lower jaw, and was typically shorter than the upper pair, and often closely placed together, perhaps making it an effective tool for scraping at bark or scooping up weeds.
A typical example of the gomphotheres of the day was Rhynchotherium, which lived in at least the southern parts of North America, and likely down into Central America, for much of the early Pliocene. While we have only skeletons to go on, the shape of the skull suggests that this animal did have a trunk, although it may well have been less impressive than those of modern elephants. Similarly, while it certainly had incisor teeth in the lower jaw, they were not particularly large, and it might even be a bit of a stretch to call them "tusks".
Rhynchotherium only reached as far north as Texas, Arizona, and southern California, which suggests that, like modern elephants, it preferred warm, probably fairly open and savannah-like environments. There is also a suggestion that it lived near water, perhaps along estuaries as well as large inland rivers and lakes.
The taxonomic history of the genus is somewhat complicated, since the first described specimen, which is supposed to define what the genus is, turned out to belong to something else (likely it's immediate ancestor, or something very close to it). Normally, that would mean that the name "Rhynchotherium" would have to be junked, as Brontosaurus was for a long time, but a petition to keep the name and designate a new type species was, unusually, successful. So we're allowed to say it exists.
No such confusion has related to the other two gomphotheres of Pliocene North America. Stegomastodon (despite the name, not a mastodon) and Cuvieronius were close relatives, belonging to a group of gomphotheres that had lost the lower pair of tusks, making them look rather more obviously elephant-like. One estimate puts Stegomastodon at around 260 cm (8' 6") in height, placing them somewhere in between Asian and African elephants in size, and presumably weight. Cuvieronius was likely around the same size. The tusks, however, were enormous, twisted in a spiral fashion like those of mammoths in Cuvieronius and curved dramatically upwards in Stegomastodon. In the latter at least, they reached as much as 3.5 metres (11 feet) in length - quite a bit longer than the animal was tall.
Analysis of the tooth enamel of these animals suggests that it was structurally similar to those of living elephants, and, perhaps more significantly, that they fed on a diet of mixed plants, shifting to hardier vegetation in the later Pliocene and early Pleistocene, as the climate cooled.
When the Panamanian land bridge rose, these gomphotheres headed south, becoming the only proboscideans to colonise South America. Cuvieronius, which seems to have been better able to tolerate cold climates, inhabited the Andes, while Stegomastodon took a more lowland route to the south, although still reaching all the way south to Uruguay. Even in the North, they survived long enough to live alongside early American mammoths in Arizona and New Mexico, but they lasted much longer in the South.
Indeed, in that continent, protected perhaps from the worst of the Ice Ages, they survived right through to the end of the Pleistocene. Indeed, while it is likely a drier climate during the Last Glacial Maximum that led to their eventual demise, they may well have encountered humans towards the very end.
Even in this time long before the bison - or even giant ground sloths - these proto-elephants were by no means the only large herbivores in North America. In another break with our expectations of North American wildlife, however, the other main examples... were camels.
You might wonder what the heck camels were doing in North America, but actually, the real question is why they aren't there now, since this is the continent on which they first appeared. That was long, long before the Pliocene, by which time they were already beginning to spread out into Asia, and even Africa. (The modern camels of the Sahara are a much more recent human introduction, however). But, in the Pliocene, and even into the Pleistocene, there were still camels on their home continent, before the Ice Ages finished them off, leaving them only in places they had colonised later.
Among these Pliocene camelids was Hemiauchenia, which lived across what was then savannah and dry steppeland, from Florida to California, and as far north as Nebraska. This, however, was no challenger to the gomphotheres, being a slender, long-legged animal no more than 1.8 metres (6 feet) in height, at the very most. Their low-crowned teeth suggest that they were mainly browsers, feeding on soft leaves and the like, and certainly not desert-dwellers. Like the gomphotheres, they, too crossed into South America when the continents collided, where they became the ancestors of the living llamas and other small camelids of the continent. In the North, they survived surprisingly far into the Ice Ages, likely becoming the last local camelids to die out.
This, however, was completely dwarfed by the giant camel Titanotylopus, an enormous animal that inhabited much of the modern US, from Texas to South Dakota. We don't, unfortunately, know too much about it. Presumably it wasn't a true desert-dweller, because that doesn't fit what we know of the places where it lived, but beyond that it likely resembled its modern kin in most respects. We know, for instance, that it probably walked much like modern camels do, and that it had the same sort of feet - a cloven hoof that has lost the actual hoof and replaced it with broad toes.
It was successful enough that there was more than one species, and some authors assign the later ones to a distinct genus, Gigantocamelus. It is generally thought that it probably did have a hump (which Hemiauchenia would have lacked), although this is guesswork based on its similarity to modern species and the dramatic length of the spines on its backbone. What's really remarkable, though, is that, from the bones we have, it has been estimated to stand as much as 3.5 metres (11 feet) high at the shoulder, with the head obviously quite a bit higher than that. Its long legs would have contributed a fair bit to this, and the animal certainly would not have been as heavy as the gomphotheres of the day, but it was likely over a ton, and possibly over two tons, in weight.
Which, for a camel, is pretty remarkable.
Not much, perhaps, would have eaten a fully-grown gomphothere or giant camel, unless they were scavenging from an animal that was already dead. But North America was hardly devoid of carnivores, to which I will turn in part 9.
[Picture by "sergiodlarosa" from Wikimedia Commons.]