late 14c., from Late Latin paganus "pagan," in classical Latin "villager, rustic; civilian, non-combatant" noun use of adjective meaning "of the country, of a village," from pagus "country people; province, rural district," originally "district limited by markers," thus related to pangere "to fix, fasten," from PIE root *pag- "to fix" (see pact). As an adjective from early 15c.
Religious sense is often said to derive from conservative rural adherence to the old gods after the Christianization of Roman towns and cities; but the word in this sense predates that period in Church history, and it is more likely derived from the use of paganus in Roman military jargon for "civilian, incompetent soldier," which Christians (Tertullian, c.202; Augustine) picked up with the military imagery of the early Church (e.g. milites "soldier of Christ," etc.). Applied to modern pantheists and nature-worshippers from 1908.