Old English losian "be lost, perish," from los "destruction, loss," from Proto-Germanic *lausa- (source also of Old Norse los "the breaking up of an army;" Old English forleosan "to lose, destroy," Old Frisian forliasa, Old Saxon farliosan, Middle Dutch verliesen, Old High German firliosan, German verlieren, as well as English -less, loss, loose). The Germanic word is from PIE *leus-, an extended form of root *leu- "to loosen, divide, cut apart."
The verb also is merged with, or has taken the (weaker) sense of, the related Middle English leese "be deprived of, lose" (Old English leosan, a class II strong verb whose past participle loren survives in forlorn and love-lorn), from Proto-Germanic *leusanan (source also of Old High German virliosan, German verlieren, Old Frisian urliasa, Gothic fraliusan "to lose").
Hence lose in the transitive senses "part with accidentally, be deprived of, miss the possession or knowledge of" (money, blood, sleep, hair, etc.), c. 1200; "fail to keep, lose track of" (mid-13c.). Meaning "fail to preserve or maintain" is from mid-15c. Meaning "fail to gain or win" (something) is from c.1300; intransitive meaning "fail to win" (a game, contest, lawsuit, etc.) is from late 14c. Meaning "to cause (someone) to lose his way" is from 1640s; meaning "cease to have, be rid of" (something unwanted) is from 1660s.
To lose heart "become discouraged" is from 1744; to lose (one's) heart "fall in love" is from 1630s. To lose (one's) mind "become insane" is attested from c. 1500. To lose out "fail" is 1858, American English. To lose it "become distraught, break down and lose control of oneself" is by 1990s; the it probably being one's self-control or grip on reality. Related: Lost; losing.