Old English fleoge "a fly, winged insect," from Proto-Germanic *fleugon "flying insect" (source also of Old Saxon fleiga, Old Norse fluga, Middle Dutch vlieghe, Dutch vlieg, Old High German flioga, German Fliege "fly"); literally "the flying (insect)" (compare Old English fleogende "flying"), from PIE root *pleu- "to flow," which is also the source of fly (v.1).
Originally any winged insect (moths, gnats, beetles, locusts, hence butterfly, etc.) and long used by farmers and gardeners for any insect parasite. Flies figuratively for "large numbers" of anything is from 1590s. Plural flien (as in oxen, etc.) gradually normalized 13c.-15c. to -s. Fly in the ointment is from Eccles. x:1. Fly on the wall "unseen observer" first recorded 1881. No flies on _____ "no lack of activity or alertness on the part of," is attested by 1866. Meaning "fish-hook dressed to resemble an insect" is from 1580s; Fly-fishing is from 1650s. Fly-catcher "bird which eats insects on the wing" is from 1670s. The fly agaric mushroom (1788) so called because it was used as a poison for flies.
The sense of "a flight, flying" is from mid-15c. From the verb and the notion of "flapping as a wing does" comes the noun sense of "tent flap" (1810), which was extended to "strip of material sewn into a garment as a covering for buttons" or some other purpose (1844). Baseball fly ball attested by 1866. To do something on the fly is 1856, apparently from baseball.
When the catcher sees several fielders running to catch a ball, he should name the one he thinks surest to take it, when the others should not strive to catch the ball on the fly, but only, in case of its being missed, take it on the bound. ["The American Boys Book of Sports and Games," New York, 1864]