Erstmals wird die Siedlung walahse im Jahr 926 im Kontext der Ungarneinfälle erwähnt. Kaiser Friedrich I. bestätigte 1181 eine dort ansässige Klerikergemeinschaft als Augustinerchorherren-Stift bevor Waldsee im Jahr 1298 durch König Albrecht I. zur Stadt erhoben wurde. Anfänglich herrschten die Herren von Wallsee über die Stadt, die zunächst Ministeriale (Dienstmannen) der Welfen und Staufer waren. Nachdem diese ab 1278 in die Dienste König Rudolfs I. traten und schließlich in die österreichischen Erblande (erbliche Besitztümer des Hauses Habsburg im Heiligen Römischen Reich) übersiedelten, verkauften sie Waldsee 1331 an die österreichischen Herzöge Albrecht II. und Otto von Habsburg.

Daraufhin verpfändeten die Habsburger Waldsee in den Jahren 1386 bzw. 1402 an die Truchsessen von Waldburg. Diese Pfandherrschaft führte zu zahlreichen Konflikten zwischen den Truchsessen und den Bürgern Waldsees, die sich stets den Habsburgern zugehörig fühlten, aber auch zu Konflikten um die Macht in der Pfandschaft zwischen den Truchsessen von Waldburg und den Habsburgern. Schließlich löste sich die Stadt 1680 selbst aus der Pfandschaft aus blieb bis zum Ende des Alten Reiches (1803/1806) unter der Herrschaft Österreichs. Danach wurde Waldsee in das Königreich Württemberg eingegliedert.