mid-14c., complexioun, "temperament, natural disposition of body or mind," from Old French complexion, complession "combination of humors," hence "temperament, character, make-up," from Latin complexionem (nominative complexio) "combination" (in Late Latin, "physical constitution"), from complexus "surrounding, encompassing," past participle of complecti "to encircle, embrace," in transferred use, "to hold fast, master, comprehend," from com "with, together" (see com-) + plectere "to weave, braid, twine, entwine," from PIE *plek-to-, suffixed form of root *plek- "to plait."
The Middle English sense is from the old medicine notion of bodily constitution or general nature resulting from blending of the four primary qualities (hot, cold, dry, moist) or humors (blood, phlegm, choler, black choler). The specific meaning "color or hue of the skin of the face" developed by mid-15c. In medieval physiology, the color of the face was believed to indicate temperament or health. The word rarely is used in the sense of "state of being complex."