c. 1200, remedie, "means of counteracting sin or evil of any kind; cure for a vice or temptation;" late 14c., "a cure for a disease or disorder, medicine or process which restores health;" from Anglo-French remedie, Old French remede "remedy, cure" (12c., Modern French remède) and directly from Latin remedium "a cure, remedy, medicine, antidote, that which restores health," from re-, here perhaps an intensive prefix (or perhaps literally, "again;" see re-), + mederi "to heal" (from PIE root *med- "take appropriate measures").
Figurative use is from c. 1300. The meaning "legal redress; means for obtaining justice, redress, or compensation through a court" is by mid-15c.
c. 1400, remedien, "effect a cure, cure;" also "put right, rectify, remove something evil from; give legal redress," from Old French remedier or directly from Latin remediare, from remedium (see remedy (n.)). Related: Remedied; remedying; remediless.