This word for non-Christian or pagan is common in all the Germanic languages. It appears in Old English in the year 826. From the Charter of Ecgberht from that year:
Andlang dic to ðem heðenum birithelsum.
(All along the dike to the heathen city.)
The word clearly arose after the introduction of Christianity to the German tribes, but had to be quite early for it to appear in all the Germanic tongues, sometime in the 4th century or earlier.
It is believed to have originated in Gothic and spread to the other Germanic tribes. In the 4th century, Ulfilas, bishop of the Goths, translated the Greek Bible into Gothic, fragments of which survive. In Mark 7:26, which reads “Now the woman was a Greek, a Syrophoenician by birth...” Ulfilas used the word haiþnô in place of Greek, or as it appears in the Vulgate gentilis, or gentile. Haiþnô literally means dweller on the heath. So the original sense is remarkably the same as the modern sense, someone living beyond the bounds of civilization and who has not received the word of God.
This hypothesis is not universally accepted however. Some point out that Ulfilas may have been influenced by Armenian and that heathen instead is related to the Armenian het’anos, which is derived from the Greek ethnos, meaning nation or people.
(Source: Oxford English Dictionary, 2nd Edition)
Copyright 1997-2015, by David Wilton