early 14c., "to carry out, fulfill" (transitive), probably from Old French compli, past participle of complir "to accomplish, fulfill, carry out," from Vulgar Latin *complire, from Latin complere "to fill up," transferred to "fulfill, finish (a task)," from com-, here probably as an intensive prefix (see com-), + plere "to fill" (from PIE root *pele- (1) "to fill").
Intransitive sense of "to consent, act in accordance with another's will or desire" is attested from c. 1600 and might have been influenced by ply (v.2), or perhaps it is a reintroduction from Italian, where complire had come to mean "satisfy by 'filling up' the forms of courtesy" (compare compliment (n.)).