Old English missan "fail to hit, miss (a mark); fail in what was aimed at; escape (someone's notice)," from Proto-Germanic *missjan "to go wrong" (source also of Old Frisian missa, Middle Dutch, Dutch missen, German missen "to miss, fail"), from *missa- "in a changed manner," hence "abnormally, wrongly," from PIE root *mei- (1) "to change, go, move." Reinforced or influenced by cognate Old Norse missa "to miss, to lack." Related: Missed; missing.
Sense of "fail to find" (someone or something) is by late 12c. Meaning "fail to note, perceive, or observe" is from early 13c. Meaning "fail to reach or attain what one wants" is from mid-13c. Sense of "perceive with regret the absence or loss of (something or someone)" is from c. 1300. Meaning "omit, leave out, skip" is by mid-14c. Sense of "to escape, avoid" is from 1520s.
Sense of "to not be on time for" is from 1823; to miss the boat in the figurative sense of "be too late for" is from 1929, originally nautical slang. To miss out (on) "fail to get" is by 1929.