1520s, "taste, flavor," alteration of reles "scent, taste, aftertaste," (c. 1300), from Old French relais, reles, "something remaining, that which is left behind," from relaisser "to leave behind," from Latin relaxare "loosen, stretch out," from re- "back" (see re-) + laxare "loosen," from PIE root *sleg- "be slack, be languid." Meaning "enjoyment of the taste or flavor of something" is attested from 1640s. Sense of "condiment, that which imparts flavor" is first recorded 1797. The stuff you put on hot dogs is a sweet green pickle relish.
1560s "give flavor to" (implied in relished), from relish (n.). The transferred sense of "to enjoy, take pleasure in" is from 1590s. Related: Relishing.