This is an interesting case that might have never been discovered had it not been for another effect of high fluoride levels in water. Here's the (relatively well-known) history.
In 1901, after graduating from dental school, Dr. Frederick McKay moved from the east coast USA to Colorado Springs, Colorado to start a dental practice. When he reached there, he noticed that most of the children had very darkened, ugly teeth. This condition is now understood to be dental fluorosis. The stains were permanent and appeared severe, but there was no mention of such condition in the dental literature. McKay eventually gathered enough interest in the condition, then called "Colorado Brown Stain", to get the interest of a more senior researcher Dr. G.V. Black, who was initially skeptical but quickly got interested after observing the condition and realizing that it affected about 90% of the children in the area. Black and McKay experimented on this until Black's death in 1915, after which McKay continued. One of the surprising results of these experiments was that the children with this condition were actually less prone to cavities and tooth decay than others.
In 1923, McKay was able to perform an experiment that demonstrated that something in the water was causing the condition. The town of Oakley, Idaho had just installed a new water pipeline, and the Colorado Brown Stain had begun to show up there afterwards. McKay already had a hunch the water might have something to do with it, so he convinced the town's leaders to use a different water source. Within a few years the condition had all-but disappeared. McKay still didn't know what the difference was in the water, but after he and Dr. Grover Kempf from the United States Public Health Service investigated a third case in Bauxite, Arkansas, they were sure it was in the water.
At this point, H. V. Churchill, an industrial chemist from ALCOA, was worried that the results would hurt his business, so he decided to collect samples from Bauxite and run more sophisticated tests. The results were surprising: high levels of fluoride, which was not known to be present in the water supply at all at the time. After some further tests of other locations in collaboration with McKay, in 1931 they had reached the surprising conclusion that indeed this was caused by high levels of fluoride.
The application of this wasn't fully realized until the 1940s, when more precise measurements of fluoride levels in water showed that sufficiently low levels only very rarely caused fluorosis. Dr. Henry Trendley Dean came to the realization that at these low levels, cavity reduction demonstrated by Black and McKay might still be possible. After performing large-scale tests in several cities (the first of which was Grand Rapids, Michigan), this was definitively demonstrated.
Like I said, this story is fairly well-known and documented in several locations. Wikipedia has an article on fluoridation with some history. More extensive histories are compiled by the National Institute of Dental and Craniofacial Research, by the Centers for Disease Control and Prevention, and by Nature.