c. 1600, from heathen + -ism. Old English words for it included hæðennes, hæðendom, and a later ones were heathenship (late Old English), heathenhood (late 13c.), heathenry (1560s).
heated
heater
heath
heathen
heathenish
heathenism
heather
heating
heave
heaven
heavenly