1400年頃、恐らく14世紀中頃、「キリスト教徒でもユダヤ教徒でもない信仰を持つ人」という意味で使われるようになりました。この語は後期ラテン語のpaganus（「異教徒」）から来ており、古典ラテン語では「村人」「田舎者」「民間人」「非戦闘員」といった意味を持つ名詞として使われていました。これは形容詞として「田舎の」「村の」を意味し、pagus（「田舎の人々」「地方」「農村地区」）から派生しています。元々は「境界で区切られた地区」を指し、pangere（「固定する」「留める」）とも関連しています（この語は印欧語根*pag-「固定する」から来ています）。形容詞として使われるようになったのは15世紀初頭からです。
この宗教的な意味合いは19世紀に入ってから、特に田舎の保守的な人々がキリスト教化されたローマの町や都市に残っていた古い神々への信仰から来ていると言われることがありました（例：Trench）。しかし、このラテン語の用法は教会の歴史においてその時期よりも前から存在しており、むしろローマ軍の軍事用語として「民間人」「無能な兵士」を指すために使われていたpaganusが、初期のキリスト教会での軍事的な比喩（例えば、milites「キリストの兵士」など）と結びついて広まった可能性が高いです（テルトゥリアヌス、約202年；アウグスティヌス）。
英語ではその後、「キリスト教徒でもユダヤ教徒でもイスラム教徒でもない人」というより狭い意味で使われるようになりました。1841年には「異教的な性質や習慣を持つ人」として使われるようになり、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]
Paganとheathenは基本的に同じ意味ですが、paganは時に、偽の神々を崇拝しながらもより教養のある民族（例えばギリシャ人やローマ人）に特有に使われ、heathenは未開の偶像崇拝者（アフリカの部族など）を指すことがあります。ムスリムはpaganとは見なされず、ましてやheathenとは考えられません。[Century Dictionary, 1897]
英語の姓Paine、Payneなどは古い記録によればラテン語のpaganusに由来するとされていますが、「村人」「田舎者」「異教徒」のどの意味から来ているのかは議論されています。また、13世紀には一般的なキリスト教名としても使われており、「その意味を考えずに名付けられたに違いない」とされています（「Dictionary of English Surnames」）。
