Old English fox "a fox," from Proto-Germanic *fuhsaz "fox" (cognates Old Saxon vohs, Middle Dutch and Dutch vos, Old High German fuhs, German Fuchs, Old Norse foa, Gothic fauho), from Proto-Germanic *fuh-, from PIE *puk- "tail" (source also of Sanskrit puccha- "tail").
The bushy tail also inspired words for "fox" in Welsh (llwynog, from llwyn "bush"); Spanish (raposa, from rabo "tail"); and Lithuanian (uodegis, from uodega "tail"). Metaphoric extension to "clever person" was in late Old English. Meaning "sexually attractive woman" is from 1940s; but foxy in this sense is recorded from 1895. A fox-tail was anciently one of the badges of a fool (late 14c.).
A late Old English translation of the Medicina de Quadrupedibus of Sextus Placitus advises, for women "who suffer troubles in their inward places, work for them into a salve a foxes limbs and his grease, with old oil and with tar; apply to the womens places; quickly it healeth the troubles." It also recommends, for sexual intercourse without irritation, "the extremest end of a foxes tail hung upon the arm." Rubbing a fox's testicles on warts was supposed a means to get rid of them.