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.