Waldstetten wurde im Jahre 1275 in der Zehntsteuerliste der Diözese Konstanz, dem "liber decimationis", erstmals urkundlich erwähnt. Die Pfarrei Waldstetten gehörte damals zum Dekanat Süßen und zum Bistum Konstanz, der Ort selbst den Herren von Rechberg.

Im Städtekrieg von 1449 wurde die rechbergsche Burg auf dem Eichhölzle bei Waldstetten vom Heer aus Gmünd und Hall belagert und zerstört. 1672 wurde das Rittergut Waldstetten an die Grafen von Gravenegg verkauft, die es 1699 an das Stiftskapitel der Propstei Ellwangen weiter veräußerten.

Im Jahre 1802 fielen im Zuge der Säkularisation alle Besitztümer der Propstei Ellwangen an das Haus Württemberg, somit auch Waldstetten.1824 erhielt Waldstetten das Marktrecht verliehen. In den beiden Weltkriegen 1914 bis 1918 und 1939 bis 1945 mussten viele Gefallene und Vermisste verzeichnet werden. In der Nachkriegszeit kam der wirtschaftliche Aufschwung, die Infrastruktur wurde erheblich verbessert.

Waldstetten konnte bei der Gemeindereform Anfang der 70er Jahre seine Selbständigkeit bewahren. Im Jahr 2000 wurde Waldstetten als staatlich annerkannter Erholungsort ausgezeichnet.

Wißgoldingen wurde ebenfalls 1275 im "liber decimationis" erstmal urkundlich erwähnt und gehörte den Herren von Rechberg. Im Dreißigjährigen Krieg wurde der Ort schwer heimgesucht; durch Hunger und Seuchen kam die Hälfte der Dorfbewohner um. Nach dem Aussterben des Mannesstammes der Donzdorfer Linie bei den Rechbergern verkauften die Schwestern des letzten Grafen das Rittergut Wißgoldingen im Jahre 1735 an Württemberg, 1742 wurde es den Herren von Holtz aus Alfdorf weiterveräußert. 1972 wurde Wißgoldingen nach Waldstetten eingegliedert.