Der Gründungssage nach lag der Ursprung der Stadt im Jahre 330. Emerius, ein Gesandter der Kaiserin Helena, soll danach der erste der Herren von Waldsee gewesen sein. Das älteste Dokument, das über Waldsee berichtet, der Weißenburger Codex, nennt das Jahr 926, als die Ungarn in "Walahsé" eine königliche Niederlassung zerstörten. Für die Könige des frühen Mittelalters war Walahsé günstig gelegen, da die Römer eine Straße vom Bodensee zur Donau zwischen den beiden Seen hindurch gebaut hatten.

Der Name, der mit ziemlicher Sicherheit aus dem 4. Jahrhundert stammt, ist nicht auf Wald und See zurückzuführen, sondern auf das althochdeutsche "walh", in dem das Wort "welsch" (fremd) zu erkennen ist. Die Walchen waren der keltische Stamm, der Süddeutschland bewohnte.

1298 verleiht König Albrecht I. den Waldseern die Stadtrechte. Rund 30 Jahre später wurde Stadt und Herrschaft schließlich an Österreich verkauft, welches Waldsee 1386 an den Truchsess Johann von Waldburg verpfändete. Die Bevölkerung der Stadt litt sehr unter der strengen Herrschaft und versuchte sich durch Aufstände wiederholt aus der Pfandschaft zu lösen. Nach all den Demütigungen galt das kostbare Rathaus, das 1424-1426 entstand, die Stadtummauerung und die Frauenbergkirche als Zeichen von Stärke und Selbstbewusstsein.

300 Jahre lang kämpfte Waldsee darum wieder unmittelbar zu Österreich zu gehören. Doch erst 1680 gelang es Waldsee und den anderen vier "Vorderösterreichischen Donaustädten" Saulgau, Mengen, Riedlingen und Munderkingen sich von der Waldburgischen Pfandherrschaft freizukaufen. Bis 1806 gehörte Waldsee dann zu Österreich. Zu den wohl bekanntesten Persönlichkeiten dieser Zeit gehören die Selige Gute Beth, Hans Zürn sowie Truchsess Georg III. – genannt Bauernjörg -, der 1525 den Aufstand von Bauern in fast allen Teilen des Reiches niederschlug.

Durch Napoleons Veränderungen des europäischen Staatengefüges verlor Österreich seine vorderösterreichischen Besitzungen. Waldsee kam zu Württemberg und wurde 1807 Oberamtsstadt. Doch die Armut hielt weiter an. Als Zeichen des Aufbruchs ist ab 1811 der Abbruch der beengenden Stadtmauern zu sehen. Die Schule kam unter staatliche Obhut, 1834 erhielt Waldsee seine erste Zeitung, es folgten ersten Straßenlaternen und 1869 schließlich die Eisenbahn.

Seit 1938 gehört Waldsee zum Kreis Ravensburg, 1972 kamen die Ortsteile Gaisbeuren, Mittelurbach und Reute zu Waldsee. 1975 werden Haisterkirch und Michelwinnaden eingemeindet.