c. 1200, "medical treatment, cure, remedy," also used figuratively, of spiritual remedies, from Old French medecine (Modern French médicine) "medicine, art of healing, cure, treatment, potion," from Latin medicina "the healing art, medicine; a remedy," also used figuratively, perhaps originally ars medicina "the medical art," from fem. of medicinus (adj.) "of a doctor," from medicus "a physician" (from PIE root *med- "take appropriate measures"); though OED finds evidence for this is wanting. Meaning "a medicinal potion or plaster" in English is mid-14c.
To take (one's) medicine "submit to something disagreeable" is first recorded 1865. North American Indian medicine-man "shaman" is first attested 1801, from American Indian adoption of the word medicine in sense of "magical influence." The U.S.-Canadian boundary they called Medicine Line (first attested 1910), because it conferred a kind of magic protection: punishment for crimes committed on one side of it could be avoided by crossing over to the other. Medicine show "traveling show meant to attract a crowd so patent medicine can be sold to them" is American English, 1938. Medicine ball "stuffed leather ball used for exercise" is from 1889.
It is called a "medicine ball" and it got that title from Prof. Roberts, now of Springfield, whose fame is widespread, and whose bright and peculiar dictionary of terms for his prescription department in physical culture is taught in every first-class conducted Y.M.C.A. gymnasium in America. Prof. Roberts calls it a "medicine ball" because playful exercise with it invigorates the body, promotes digestion, and restores and preserves one's health. ["Scientific American Supplement," March 16, 1889]