device to make an air current, Old English fann (West Saxon) "a basket or shovel for winnowing grain" (by tossing it in the air), from Latin vannus, perhaps related to ventus "wind" (see wind (n.1)), or from PIE root *wet- (1) "to blow" (also "to inspire, spiritually arouse;" see wood (adj.)). Old English did not have a letter -v-, hence the change in the initial consonant.
The chaff, being lighter, would blow off. Sense of "device for moving air" first recorded late 14c.; the hand-held version is first attested 1550s. A fan-light (1819) was shaped like a lady's fan. The automobile's fan-belt is from 1909. Fan-dance is from 1872 in a Japanese context; by 1937 as a type of burlesque performance.