Old English hæðen "not Christian or Jewish," also as a noun, "heathen man, one of a race or nation which does not acknowledge the God of the Bible" (especially of the Danes), merged with Old Norse heiðinn (adj.) "heathen, pagan," from Proto-Germanic *haithana- (source also of Old Saxon hedhin, Old Frisian hethen, Dutch heiden, Old High German heidan, German Heiden), which is of uncertain origin.
Perhaps literally "dweller on the heath, one inhabiting uncultivated land;" see heath + -en (2). Historically assumed to be ultimately from Gothic haiþno "gentile, heathen woman," used by Ulfilas in the first translation of the Bible into a Germanic language (as in Mark vii.26, for "Greek"); like other basic words for exclusively Christian ideas (such as church) it likely would have come first into Gothic and then spread to other Germanic languages. If so it could be a noun use of an unrelated Gothic adjective (compare Gothic haiþi "dwelling on the heath," but a religious sense is not recorded for this).
Whether native or Gothic, it might have been chosen on model of Latin paganus, with its root sense of "rural" (see pagan), but that word appears relatively late in the religious sense. Or the Germanic word might have been chosen for its resemblance to Greek ethne (see gentile), or it may be a literal borrowing of that Greek word, perhaps via Armenian hethanos [Sophus Bugge]. Boutkan (2005) presents another theory:
It is most probable that the Gmc. word *haiþana- referred to a person living on the heath, i.e. on common land, i.e. a person of one's own community. It would then be a neutral word used by heathen people in order to refer to each other rather than a Christian, negative word denoting non-Christians.
early 13c., painime, paynyme, "heathen lands collectively," from Old French paienime, paienisme "heathen, pagan; Saracen lands or culture or faith," from Late Latin paganismus "heathendom" (Augustine), from paganus "heathen" (see pagan). The original sense is obsolete; the mistaken meaning "a heathen person" (c. 1300, also in Old French) is via phrases such as paynim lands. As an adjective, "non-Christian, pagan," c. 1300, from Old French.
late 14c., "a heathen, a Saracen, a pagan, an unbeliever, a non-Christian," from miscreant (adj.) or from Old French mescreant, which had also a noun sense of "infidel, pagan, heretic." Sense of "villain, vile wretch, scoundrel" is first recorded 1590 in Spenser.
one of the Old Testament people of coastal Palestine who made war on the Israelites, early 14c., from Old French Philistin, from Late Latin Philistinus, from Late Greek Philistinoi (plural), from Hebrew P'lishtim, "people of P'lesheth" ("Philistia"); compare Akkadian Palastu, Egyptian Palusata; the word probably is the people's name for themselves. Hence, "a heathen enemy, an unfeeling foe" (c. 1600).
c. 1400, perhaps mid-14c., "person of non-Christian or non-Jewish faith," from Late Latin paganus "pagan," in classical Latin "villager, rustic; civilian, non-combatant" noun use of adjective meaning "of the country, of a village," from pagus "country people; province, rural district," originally "district limited by markers," thus related to pangere "to fix, fasten," from PIE root *pag- "to fasten." As an adjective from early 15c.
The religious sense often was said in 19c. [e.g. Trench] to derive from conservative rural adherence to the old gods after the Christianization of Roman towns and cities; but the Latin word in this sense predates that period in Church history, and it is more likely derived from the use of paganus in Roman military jargon for "civilian, incompetent soldier," which Christians (Tertullian, c. 202; Augustine) picked up with the military imagery of the early Church (such as milites "soldier of Christ," etc.).
The English word was used later in a narrower sense of "one not a Christian, Jew, or Muslim." As "person of heathenish character or habits," by 1841. Applied to modern pantheists and nature-worshippers from 1908.
Pagan and heathen are primarily the same in meaning; but pagan is sometimes distinctively applied to those nations that, although worshiping false gods, are more cultivated, as the Greeks and Romans, and heathen to uncivilized idolaters, as the tribes of Africa. A Mohammedan is not counted a pagan much less a heathen. [Century Dictionary, 1897]
The English surname Paine, Payne, etc., appears by old records to be from Latin paganus, but whether in the sense "villager," "rustic," or "heathen" is disputed. It also was a common Christian name in 13c., "and was, no doubt, given without any thought of its meaning" ["Dictionary of English Surnames"].
a name given in the southwest of England to a large sandstone boulder, by 1743, properly sarsen stone, that is, "Saracen stone," from Saracen in the old, broad sense of "pagan, heathen" and thus used generally in the popular mind for the former (pre-Christian) inhabitants of the region.
The same word was applied to the ancient leavings outside Cornish tin mines, also known as Jews' pits, those being the other people formerly credited in Western Europe with any ancient structure of forgotten origin, based vaguely on Biblical chronologies.