c. 1300, "strange, foreign," from Old French alien "strange, foreign;" as a noun, "an alien, stranger, foreigner," from Latin alienus "of or belonging to another, not one's own, foreign, strange," also, as a noun, "a stranger, foreigner," adjective from alius (adv.) "another, other, different," from PIE root *al- (1) "beyond."
Meaning "residing in a country not of one's birth" is from mid-15c. Sense of "wholly different in nature" is from 1670s. Meaning "not of this Earth" first recorded 1920. An alien priory (mid 15c.) is one owing obedience to a religious jurisdiction in a foreign country.