From the 4th century Gothic Bible:

Mark 7:26
wasuž-žan so qino haižno, Saurini fwnikiska gabauržai, jah baž ina ei žo unhulžon uswaurpi us dauhtr izos.

— The woman was a Greek, a Syrophenician by nation; and she besought him that he would cast forth the devil out of her daughter.
— ἡ δὲ γυνὴ ἦν ἑλληνίς, συροφοινίκισσα τῷ γένει: καὶ ἠρώτα αὐτὸν ἵνα τὸ δαιμόνιον ἐκβάλῃ ἐκ τῆς θυγατρὸς αὐτῆς.


This is the very first attested usage of a word cognate to Modern English heathen.

The etymology of the Gothic haižno is disputed, but either one of these two answers is likely to be right:

  1. Haižno stems from haiži, "heath". In this case haižno would mean "heath-dweller", a construction similar to that of the Latin paganus, meaning "country dweller", "villager". An explanation for Wulfila's possible use of haižno in this sense is found here:
    The woman was an outsider. She was a Greek, born in Syrian Phoenicia, definitely not one of the Jews to whom Jesus had been ministering. Chapter 7 of the Book of Mark tells us that Jesus met her when he went up the Mediterranean coast to the vicinity of Tyre and Sidon. There this woman asked Jesus to drive out a demon in her daughter. He hesitated to heal anyone other than his own people, saying rather harshly, "Let the children first be fed, for it is not right to take the children's bread and throw it to the dogs." But the foreign woman had a ready answer: "Even the dogs under the table eat the children's crumbs." That was enough. "For this saying you may go your way; the demon has left your daughter," said Jesus, and it was so.

    Three centuries later, when Bishop Wulfilas of the Visigoths was translating this story into his native tongue, he described the woman's otherness by saying she was haithno, our heathen. This may just have been to say she was figuratively living on the heath, out in the countryside away from the community. But apparently thanks to Wulfilas's choice of words, the religious meaning of heathen as "outside the faith" spread to the other Germanic languages, including English, as they changed their allegiance from heathen to Christian. The word appears in English sermons written as long ago as the year 971.
    Development in the meaning of the word followed, as it spread to other Germanic languages, through the centuries. From wikipedia:
    Heathen (Old English hęšen, Old Norse heišinn) was coined as a translation of Latin paganus, in the Christian sense of "non-Abrahamic faith".

    In the Sagas, the terms heišni and kristni (Heathenry and Christianity) are used as polar terms to describe the older and newer faiths. Historically, the term was influenced by the Gothic term *haiži, appearing as haižno in Ulfilas' bible for translating gunē Hellēnis, "Greek (i.e. gentile) woman" of Mark 7:26, probably with an original meaning "dwelling on the heath", [...]
    Later on, the word heathen, and its cognates, gained the current meaning of "non-Abrahamic".


  2. Haižno was borrowed from the Armenian hethanos, which by its turn was borrowed from the Greek ethnikos. An explanation for this choice can be found in wikipedia:
    [...] ethnikos was used as the LXX translation of Hebrew goyim "the nations, non-Hebrews, non-Jews".
    Since Wulfila translated his Bible from Greek, it's possible Wulfila was aware of the usage of the word ethnikos in the Septuagint, and borrowed it to Gothic.


A third alternative, combining the other two is also possible: Wulfila chose the word haižno, with the sense of alternative 1, but influenced by Greek, for the similarity to Greek ethne, translated as "gentile" in a biblical context.

What is clear anyway, is that the first usage of a word cognate to heathen was to describe a non-Abrahamic, Hellenic woman, born in Syrian Phoenicia.