1530s, "a statement contrary to common belief or expectation," from Middle French paradoxe (14c.) and directly from Latin paradoxum "paradox, statement seemingly absurd yet really true," from Greek paradoxon "incredible statement or opinion," noun use of neuter of adjective paradoxos "contrary to expectation, incredible," from para- "contrary to" (see para- (1)) + doxa "opinion," from dokein "to appear, seem, think" (from PIE root *dek- "to take, accept").
Originally with notions of "absurd, fantastic." Meaning "statement that is seemingly self-contradictory yet not illogical or obviously untrue" is from 1560s. Specifically in logic, "a statement or proposition from an acceptable premise and following sound reasoning that yet leads to an illogical conclusion," by 1903.