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.
Related entries & more 
heathenish (adj.)
Old English hæðenisc; see heathen + -ish. Related: Heathenishly; heathenishness. Similar formation in Dutch heidensch, Old High German hiedanisc, German heidenisch.
Related entries & more 
heathenism (n.)
c. 1600, from heathen + -ism. Old English words for it included hæðennes, hæðendom, and a later ones were heathenship (late Old English), heathenhood (late 13c.), heathenry (1560s).
Related entries & more 
hoyden (n.)
"ill-bred, boisterous young female," 1670s; earlier "rude, boorish fellow" (1590s), of uncertain origin; perhaps from Dutch heiden "rustic, uncivilized man," from Middle Dutch heiden "heathen," from Proto-Germanic *haithinaz- (see heathen). OED points to Elizabethan hoit "indulge in riotous and noisy mirth" in Nares.
Related entries & more 
paynim (n.)

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.

Related entries & more 
miscreant (n.)

late 14c., "a heathen, a Saracen, a pagan, an unbeliever, a non-Christian," from miscreant (adj.) or from Old French mescreant, which also had a noun sense of "infidel, pagan, heretic." Sense of "villain, vile wretch, scoundrel" is first recorded 1590 in Spenser.

Related entries & more 

early 12c., sancte Martines mæsse, the church festival formerly held on Nov. 11 in honor of the patron saint of France, St. Martin, late 4c. bishop of Tours noted for destroying the remaining heathen altars. Also see mass (n.2).

Related entries & more 
pagan (n.)

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"].

Related entries & more 
sarsen (n.)

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.

Related entries & more 
white (n.)

Old English hwit "whiteness, white food, white of an egg," from white (adj.). Also in late Old English "a highly luminous color devoid of chroma." Meaning "white part of the eyeball" is from c. 1400. Meaning "white man, person of a race distinguished by light complexion" is from 1670s; white man in this sense is from 1690s. White man's burden is from Kipling's 1899 poem:

Take up the White Man's burden—
The savage wars of peace—
Fill full the mouth of Famine
And bid the sickness cease;
And when your goal is nearest
The end for others sought,
Watch sloth and heathen Folly
Bring all your hopes to nought.
Related entries & more