late 14c. as an adjective, "perplexed, puzzled, bewildered," from Latin perplexus "involved, confused, intricate;" but Latin had no corresponding verb *perplectere. The Latin compound would be per "through" (from PIE root *per- (1) "forward," hence "through") + plexus "entangled," past participle of plectere "to twine, braid, fold" (from suffixed form of PIE root *plek- "to plait").
The form of the English adjective shifted to perplexed by late 15c., probably to conform to other past-participle adjectives. The verb is latest attested of the group, in 1590s, evidently a back-formation from the adjective. Related: Perplexing, which well describes the history of the word.