mid-14c., comenden, "praise, mention approvingly," from Latin commendare "to commit to the care or keeping (of someone), to entrust to; to commit to writing;" hence "to set off, render agreeable, praise," from com-, here perhaps an intensive prefix (see com-), + mandare "to commit to one's charge" (see mandate (n.)). A doublet of command.
Sense of "commit, deliver with confidence" in English is from late 14c. Meaning "bring to mind, send the greeting of" is from c. 1400. The "praise" sense is from the notion of "present as worthy of notice or regard;" also in some cases probably a shortening of recommend. Related: Commended; commending.