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.