"Native North American shaman," by 1801, from adoption of the word medicine in native speech with a sense of "magical influence; something supposed to possess curative, supernatural, or mysterious power." The U.S.-Canadian boundary they called the Medicine Line (attested by 1880), 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. Compare Middle English use of medicine in secondary senses of "moral, psychological, or social remedy; safeguard, defense."
Unless some understanding is arrived at between the American and Canadian Governments that offenders may be promptly and vigorously dealt with, I very much fear that killing and stealing will increase to such an extent that the country along the border will be scarcely habitable. When the Indians are made to understand that the mere fact of "hopping" across the line does not exempt them from punishment, there will be a much greater guarantee of their good behaviour. Now they call the boundary the "Medicine line," because no matter what they have done upon one side they feel perfectly secure after having arrived upon the other. [Report of Superintendent L.N.F. Crozier, Dec. 1880, in "North-West Mounted Police Force Commissioner's Report," 1880]
Hence also medicine bag "pouch containing some article supposed to possess curative or magical powers, worn on the person by native North American people" (1802).