1796, a name for the French fop or dandy of the period of the Directory (1795-1799),  from French incroyable, literally "incredible" (15c.), from in- "not, opposite of, without" (see in- (1)) + croire "to believe," from Latin credere "to believe" (see credo). Said to be so called from their extravagant dress, and also, according to OED, from a favorite expression among them ("C'est vraiment incroyable").

c. 1300, "non-Christian, misbelieving, pagan, infidel;" early 15c., "heretical, unbelieving," from Old French mescreant "disbelieving" (Modern French mécréant), from mes- "wrongly" (see mis- (2)) + creant, present participle of creire "believe," from Latin credere "to believe" (see credo). Meaning "villainous, vile, detestable" is from 1590s. Related: Miscreance; miscreancy.

c. 1300, recreaunt, "confessing oneself to be overcome or vanquished, admitting defeat, surrendering, ready to yield in a fight," also a word of surrender, from Old French recreant "defeated, vanquished, yielding, giving; weak, exhausted; cowardly" (also used as a noun), present-participle adjective from recroire "to yield in a trial by combat, surrender allegiance," literally "believe again;" perhaps on notion of "take back one's pledge, yield one's cause," from re- "again, back" (see re-) + croire "entrust, believe," from Latin credere (see credo).

Non sufficit ... nisi dicat illud verbum odiosum, quod recreantus sit. [Bracton, "De Legibus et Consuetudinibus Angliæ," c. 1260]

The extended meaning "cowardly" in English is from late 14c. The meaning "unfaithful to duty" is from 1640s. Middle English also had a verb recreien "to be cowardly, yield in battle" (mid-14c.).