1550s, from letter (n.1) + carrier.
Leto
Lett
letter
letter-bag
letter-box
letter-carrier
lettered
letter-head
lettering
letter-man
letter-opener