This place is already very old, but there are no records of the very early times. However, it might be one of the - in this region (Hegau) - numerous Alemannic housing schemes characterized by the ending "ingen".
In 965 Watterdingen was the first time mentioned in a document according to which Count Chuno of Öhningen gave the village together with other property as a gift to the Cloister of Öhningen which was donated by him. In the year 1392 Watterdingen was added to the property of the lords of Klingenberg. Those pawned the domain Blumenfeld - to which also Watterdingen belonged to - to the lords of Bodman in 1463. From 1488 Watterdingen had remained under the Teutonic commander of the knightly order Mainau until it was added to Baden in 1806.
The first mention of a parish in a document goes back to the year 1275. It may be supposed that the parish had been in the sunk hamlet Kilchstetten (Kirchstetten). Today's church was built in 1539. This date is found at the entrance to the sacristy which was the entrance to the tower in former times. It is said that the church St Gordian and Epimachus was built by the inhabitants' own means.
In the middle of the 18th century the church was converted into baroque style; at the same time new choir stalls and a new tower were set up. About 200 years ago the church was given its shape of today. In 1922 an extension was built. Both in 1978 and in 1995 it was completely renovated on its exterior.