late 14c., "one who takes the place of another," from Old French lieu tenant "substitute, deputy," literally "place holder" (14c.), from lieu "place" (see lieu) + tenant, present participle of tenir "to hold," from PIE root *ten- "to stretch." The notion is of a "substitute" for higher authority.
Specific military sense of "army officer next in rank to a captain and commanding the company in his absence" is from 1570s. Pronunciation with lef- is common in Britain, and spellings to reflect it date back to 14c., but the origin of this is a mystery (OED rejects suggestion that it comes from old confusion of -u- and -v-).
"rank or commission of a captain," 1818, from captain (n.) on the model of lieutenancy or some similar word where the -c- is etymologically justified. Earlier words in the same sense were captainry (1520s), captainship (mid-15c.).