The animals that they most resemble are probably anteaters, especially the smaller species. At one time, they were even classified together with the anteaters, but there are some significant skeletal differences, especially in the structure of the backbone that indicate they are clearly distinct. Furthermore, anteaters originated in South America, while pangolins are known only from Africa and Asia, so it's long been recognised that the resemblances are actually due to parallel evolution, with the animals having a similar diet.
This leaves us with the situation that pangolins are off in a group of their own. The pangolin family is the only living family in its order, distinct from all the many larger orders of mammals - primates, rodents, cloven-footed mammals, the shrew/hedgehog/mole group, and so on. Even so, they must come from somewhere, and, for much of the 20th century, really the only way of trying to resolve this was to look at their fossil history.
Which, unfortunately, doesn't help much because the fossil record of pangolins is rather sparse. This could simply be because they aren't very common animals today, and likely never were - there weren't enough of them around to leave many fossils. Add to that the fact that they live in tropical forests, which are not good environments for fossil formation and preservation, and it's unsurprising that we don't have much to look at. But there's a further problem, which is that a key feature used in classifying mammalian fossils and assigning them to different groups is the exact shape of their teeth, especially the cheek teeth.
And pangolins don't have any teeth. So without a relatively complete fossil, it may be hard to tell that what you've got even is a pangolin.
Nonetheless, this is not to say that there is no pangolin fossil record at all. The oldest known fossils that we can place in the pangolin order date from around 47 million years ago, during the Eocene epoch (so about two-thirds of the way back to the time of the dinosaurs, quite a long way in mammalian terms). There are actually two different fossils competing for that honour, coming from the same deposits in Germany. One of these was originally identified as an anteater, and given the name Eurotamandua. It's now clear that it isn't, partly because it's hard to see how that would make sense, but also because of those differences in the structure of the spine that I mentioned earlier.
Eurotamandua wasn't literally a pangolin, in the sense of being a member of the modern pangolin family. For one thing, the fossil is sufficiently well preserved that we can be reasonably certain it didn't have any scales on its body - in life, it really would have looked a lot like an anteater. Its contemporary, Eomanis, is a different matter; while it's generally placed in a separate family, it did have scales (again, the fossil is very well preserved) and is likely much closer to modern pangolins.
The fossil Cryptomanis, from China, is a few million years younger, as is Patriomanis from North America, while Oligocene and Miocene fossils of pangolin-like animals, such as Necromanis, are found predominantly in Europe. Taken together, these lines of evidence give us good reason to suppose that pangolins originated in the Northern Hemisphere, probably in Europe, and only spread into Africa much later, when that continent met up with Eurasia towards the end of the Miocene epoch.
In the 21st century, the advance of molecular genetics has resolved the question of where pangolins fit into the mammalian family tree. It is now clear, from multiple studies, that the closest relatives of pangolins are the carnivorans - the order of mammals that includes cats, dogs, and the like. They aren't exactly close relatives, with some estimates putting the split between the two groups long before the extinction of the non-avian dinosaurs, but everything else alive today is more distant still.
That explains, at least in general terms, the ultimate origin of pangolins. But what about their more recent history? What happened to them between the end of the Miocene and today?
Today we recognise eight living species of pangolin; four each in Asia and Africa. The oldest fossil pangolin from Africa hails from South Africa and dates to 5 million years ago, just after the end of the Miocene; at least one later example is known from Uganda. Both are very similar to living forms, and may even be members of the living giant pangolin species (Smutsia gigantea). Even more recent fossils, from the Pleistocene epoch that encompassed the Ice Ages, are also known from southern Asia.
But it seemed that pangolins vanished from their original home in Europe just as they began to move to their current homes. This might not be a coincidence, since the world was cooling at the time, moving from the warmth of the Miocene to the long autumn of the Pliocene that preceded the Ice Ages. Living pangolins live in tropical environments, so it makes sense that, like some other species, they would head south as the world cooled, leaving behind Europe's cold winters just as they found more suitable habitats in Africa and India.
But that might not necessarily be so. Back in the 1930s, palaeontologist Théodor Kormos discovered what he believed to be a fossil pangolin dating back just 2 million years at a site in Hungary. It's not clear now whether or not he was correct. For one thing, the fossil consisted of only the tip of a single toe. For another, it's no longer possible to examine it to confirm whether his findings match up to modern knowledge because it was destroyed when the museum housing it was burned down during the Hungarian Revolution of 1956. No further specimen of this purported species has been discovered.
So things stood until last year when a new fossil of about the same age was described from southern Romania. This consists of a single humerus - the bone in the upper part of the forelimb - which may not be as impressive as the older fossils of the likes of Eomanis, but is certainly more than the tip of a toe. It's apparently enough to identify it, not just as belonging to a pangolin but to a previously unknown species of the genus Smutsia, which still exists today and contains two species of ground-living African pangolins.
Named S. olteniensis after the Olteţ River valley where it was found, the existence of a pangolin in Europe just as the first of the Ice Ages was about to get started raises a couple of interesting points. Firstly, there's a gap of around 12 million years between it and Necromanis, the next oldest definitive European fossil. At least some of that is surely accounted for by the fact that such fossils are likely rare and we just haven't found any from that gap - they must have been somewhere during that time, after all, and we don't know of any Asian fossils of the right age, either.
But it's also possible that at least the latest part of the apparent gap is genuine. The genus Smutsia is known only from Africa today, so it may have originated there after its ancestors headed south from Europe. Under this scenario, at some point, either during the Messinian Salinity Crisis or shortly after it finished, some members of the genus headed north again and recolonised their original home. This is, after all, known to have happened with monkeys during the Pliocene and hippos during the Pleistocene interglacials so why not pangolins?
The second interesting feature concerns exactly where it was found. Today, it's on the southern slope of the Carpathian Mountains, where the Olteţ River runs down into the Danubian Plain. Two million years ago, however, much of the present-day Danubian Plain was occupied by a lake, the last remnant of a western bay of the Black Sea that had once stretched almost to the border of present-day Serbia. Judging from the geology of the specific fossil site, at the time it was an area of relatively open woodland probably on a river valley that drained, not too much further south, into that lake.
This is not the sort of place we would expect to find any modern species of pangolin, since they prefer much warmer, heavily forested areas. Nonetheless, the ground pangolin (Smutsia temmincki) does inhabit open woodland and floodplains, albeit in the African savannah rather than the colder environment of early Pleistocene Romania. Since that's a very close relative of the extinct species, the latter plausibly had a similar lifestyle, feeding off ants in the cool woodlands before the Ice Ages forced its surviving kin back to the tropics for good.
[Photo by "flowcomm", from Wikimedia Commons.]