Um 1400, vielleicht Mitte des 14. Jahrhunderts, bezeichnete das Wort „Heide“ eine „Person, die nicht an den christlichen oder jüdischen Glauben glaubt“. Es stammt vom späten Lateinischen paganus ab, was „Heide“ bedeutet. Im klassischen Latein hatte es die Bedeutung „Dorfbewohner, Landbewohner; Zivilist, Nicht-Kämpfer“ und wurde als Substantiv aus dem Adjektiv abgeleitet, das „zum Land, zum Dorf gehörend“ bedeutete. Der Ursprung liegt im lateinischen pagus, was „Landbewohner; Provinz, ländlicher Bezirk“ bedeutet. Ursprünglich bezeichnete es ein „Gebiet, das durch Markierungen begrenzt ist“, und steht somit in Verbindung mit pangere, was „befestigen, festmachen“ bedeutet (abgeleitet von der indogermanischen Wurzel *pag-, die „befestigen“ bedeutet). Ab dem frühen 15. Jahrhundert wurde es auch als Adjektiv verwendet.
Im 19. Jahrhundert wurde oft gesagt, dass die religiöse Bedeutung des Begriffs von der konservativen ländlichen Anhängerschaft an die alten Götter nach der Christianisierung römischer Städte und Dörfer herrührte [z.B. Trench]. Allerdings ist die lateinische Verwendung in diesem Sinne älter und lässt sich eher auf den militärischen Jargon der Römer zurückführen, wo paganus „Zivilist, untauglicher Soldat“ bedeutete. Diese militärische Bildsprache übernahmen die Christen (wie Tertullian um 202 n. Chr. und Augustinus) in der frühen Kirche, etwa mit Ausdrücken wie milites („Soldat Christi“).
Im Englischen wurde das Wort später spezifischer für „jemanden, der kein Christ, Jude oder Muslim ist“. Ab 1841 fand es Verwendung als Bezeichnung für eine „Person mit heidnischem Charakter oder Brauch“. Ab 1908 wurde es auch auf moderne Pantheisten und Naturverehrer angewendet.
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]
Pagan und heathen sind im Wesentlichen gleichbedeutend; jedoch wird pagan manchmal speziell für solche Völker verwendet, die zwar falsche Götter anbeten, aber kultivierter sind, wie die Griechen und Römer. Im Gegensatz dazu bezeichnet heathen unzivilisierte Götzenanbeter, wie die Stämme Afrikas. Ein Mohammedaner wird nicht als pagan und erst recht nicht als heathen gezählt. [Century Dictionary, 1897]
Der englische Nachname Paine, Payne usw. scheint laut alter Aufzeichnungen vom lateinischen paganus abzuleiten. Ob dies nun im Sinne von „Dorfbewohner“, „Landbewohner“ oder „Heide“ geschah, ist umstritten. Im 13. Jahrhundert war es auch ein gängiger christlicher Vorname und wurde „zweifellos ohne jegliche Gedanken an seine ursprüngliche Bedeutung“ vergeben [„Dictionary of English Surnames“].
