late 14c., "means of completing; that which completes; what is needed to complete or fill up," from Old French compliement "accomplishment, fulfillment" (14c., Modern French complément), from Latin complementum "that which fills up or completes," from complere "fill up," from com-, here probably as an intensive prefix (see com-), + plere "to fill" (from PIE root *pele- (1) "to fill").
From c. 1600 as "full quality or number, full amount;" musical sense of "simple interval that completes an octave from another simple interval" is from 1873. In 16c. also having senses which were taken up c. 1650-1725 by compliment.
"make complete," 1640s, from complement (n.). Earlier in a now-obsolete sense of "exchange courtesies" (1610s), from complement (n.) in a 16c. sense "that which is added, not as necessary, but as ornamental," now going with compliment. Related: Complemented; complementing.