The story of pagan and heathen can best be told in the words of Archbishop Trench (1807-86) in his Study of Words:
You are aware that pagani, derived from (Latin) pagus, a village, had at first no religious significance, but designated the dwellers in hamlets and villages, as distinguished from the inhabitants of towns and cities.
It was, indeed, often applied to all civilians, as contradistinguished from the military caste ; and this fact may have had a certain influence when the idea of the faithful as soldiers of Christ was strongly realized in the minds of men.
But it was mainly in the following way that it became a name for those alien from the faith of Christ.
The Church fixed itself first in the seats and centers of intelligence, in the towns and cities of the Roman Empire; in them its earliest triumphs were won; while, long after these had accepted the truth, heathen superstitions and idolatries lingered on in the obscure hamlets and villages; so that pagans, or villagers, came to be applied to all the remaining votaries of the old and decayed superstitions. Heathen has run a course curiously similar.
When the Christian faith was first introduced into Germany, it was the wild dwellers on the heaths who were the last to accept it, the last probably whom it reached.