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.
"foreigner, citizen of a foreign land," early 14c., from alien (adj.) or from noun use of the adjective in French and Latin. In the science fiction sense "being from another planet," from 1953.