1540s, "acceptable, agreeable; deserving applause or approval" (senses now obsolete), from Latin plausibilis "praiseworthy, pleasing, acceptable," from plaus-, past-participle stem of plaudere "to applaud" (see plaudit). Meaning "having the appearance of truth, apparently right, seemingly worthy of acceptance or approval" is recorded from 1560s; especially "having a specious or superficial appearance of trustworthiness." Related: Plausibly.
The expression plausible deniability emerged during the Watergate scandal (1973) but is said to be from CIA jargon in the 1950s (Allen Dulles sometimes is credited with the first public use); the thing itself is older: "the situation that allows senior officials or powers to deny responsibility for discreditable actions by others in their hierarchy because no one can confirm the deniers knew of the actions."