1590s, "embarrass, puzzle, bewilder, fill (someone) with uncertainty," evidently a back-formation from perplexed, a variant of the adjective perplex (late 14c.), "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 began to shift to perplexed by late 15c., probably to conform to other past-participle adjectives, and the adjective perplex became obsolete from 17c. The verb is the latest attested of the group. The sense of "make intricate, involve, entangle, make difficult to be understood" is from 1610s. Related: Perplexing, which well describes the history of the word; perplexingly.