Medicine man was the term used to describe traditional healers and spiritual leaders of tribal cultures.
In 2268, while occupying the body of Doctor Ann Mulhall, an energy being named Thalassa described Doctor Leonard McCoy as, "a prancing, savage medicine man", in comparison to his own species. (TOS: "Return to Tomorrow")
The planet Amerind was home to a tribe of Native Americans who had been transported there by an alien species known as the Preservers. In late-2268, the medicine man of this tribe was called Salish. He was bound to marry Miramanee, the tribal priestess, in accordance to their tribal custom. (TOS: "The Paradise Syndrome")
The tribal natives of the planet Hanon IV, in the Delta Quadrant, had a medicine man who acted as their leader. Following the capture of Kes and Neelix in 2373, the medicine man tried to give Commander Chakotay a native woman in exchange for Kes. Shortly afterward, Chakotay saved one of the tribe during a volanic eruption on the planet. Subsequently, the medicine man offered to heal Ensign Samantha Wildman's newborn baby, who was suffering from lung congestion, by using native roots and plants. (VOY: "Basics, Part II")