Lindau és a Bodeni-tó környéke ősidőktől kezdve lakott terület, amit a tóban több helyen is megtalált cölöpházak maradványai bizonyítanak. A szárazföldi Aeschach városrészben a 2. vagy a 3. század elejéről származó római kori településnyomokra bukkantak.

Lindau első írásos említése 882-ből, egy Szent Galleni szerzetes tollából származik. Ez a feljegyzés egy apácakolostorra, vagy annak elődjére vonatkozik, amelynek neve "Unsere Lieben Frau unter den Linden" (Miasszonyunk a hársfák alatt) volt. A zárdát valószínűleg Adalbert, Raetia grófja építtette a 9. század elején.

Lindau nevének jelentése: "sziget, ahol hársfák nőnek". A város 13. századból származó címerében a hársfa szimbóluma máig őrzi ezt a történetet, melynek leveleinek száma a századok folyamán három és tizenöt között változott.

A város piaca 950-ből származik, és eredetileg a szárazföldön volt, de 1079-ben, az invesztitúraharcok idején biztonsági okokból a szigetre költöztették. A piacon borral, a Szent Gallen-i szerzetesek által termelt gyümölccsel és zöldséggel, valamint lennel és a hajóépítéshez szükséges kenderrel kereskedtek. A környékről zsírt, sajtot és szarvasmarhát, a sváb gazdák pedig gabonát vittek a vásárokra. A helyi kereskedelem hamarosan kiegészült a déli vidékekkel való távolsági kereskedelemmel. A 15. századtól egészen 1826-ig közvetlen kereskedelem folyt Lindau és Milánó között.

A legrégebbi építészeti alkotás a szárazföld irányába néző úgynevezett Heidenmauer, egy városfal, ami vagy a római korban, vagy a középkorban épült.

A Szent István plébániatemplom 1180-ból származik, 1224-ben pedig a ferences rendi szerzetesek alapítottak kolostort a szigeten. A gabona és sókereskedelemben meggazdagodott polgárság jogait I. Rudolf német király megerősítette, és szabad birodalmi várossá tette Lindaut.

1500 körül a pestis egyre inkább elterjedt a kereskedelmi- és zarándokutak mentén, majd a 16. század elején már Lindauban is tombolt a járványt. A tömeges halálozások hatással voltak a temetkezési kultúrára is. A fertőzéstől való félelem és a belvárosi temetők telítettsége miatt a hullákat a városfal mellett temették el. Ezekből az időkből származik az Aeschach-i "Alten Friedhof" (Öreg temető). 1635-re a környező falvakban is felütötte fejét a pestis, így a halottakat a külön erre a célra kijelölt Unterreitnau-i, Wasserburg-i és Hergensweiler-i temetőkben földelték el.

1528-ban , a reformáció idején a városi polgárság felvette az evangélikus hitet. Az 1529-es speyeri birodalmi gyűlésen a város a protestáns kisebbséget képviselő csoport oldalán állt. A polgárság Martin Bucer tanaihoz csatlakozva az evangélikus vallás szabad terjesztését követelte.

1646/7-ben a harmincéves háború idején a várost a svédek ostromolták. Max Willibald von Waldburg-Wolfegg gróf vezetésével azonban a lidauiak a ködös éjszaka folyamán lerombolták az ostromgépeket és elűzték a svédeket. A város védői a szárazföldi "Kleinen See" mocsaráig nyomultak előre. A városfal még 19. században is magán viselte az egykori ostrom lövedékeinek nyomait.

1655-ben, a harmincéves háború elmúltával rendezték meg az első lindaui Gyermekfesztivált. Az alapító Valentin Heider az ünnepségek örömét akarta visszaadni az elhanyagolt gyerekeknek. A fesztivált a mai napig minden évben megrendezik a város összes iskolájának részvételével.

1728-ban tűzvész pusztította el az óváros egy részét. Az épületeket az akkor dívó barokk stílusban építették újjá.

1802-ben, a Német-római Birodalom felbomlásának időszakában és a napóleoni háborúk idején a város elvesztette jogait, az ezeréves apácakolostort pedig szekularizálták. 1804-ben a város és a zárda Ausztriához került, majd 1806-ban az újonnan megalakult Bajor Királyság területéhez csatolták.

A hajózást 1824-ben bővítették, majd a század közepén kiépült a vasút Augsburg és Bregenz irányába. Az új kikötő 1856-ból származik az oroszlán szobrával és Bajorország egyetlen világítótornyával, amelyek azóta Lindau jelképévé váltak.

Ludwig Siebert főpolgármester 1922-ben Lindauhoz csatolta a közeli szárazföldön fekvő Aeschach, Hoyren és Reutin nevű településeket. Ugyanő lett Bajorország első nemzetiszocialista polgármestere, majd Hitler hatalomátvétele után bajor miniszterelnök 1933-tól 1942-ben bekövetkezett haláláig.

Lindau a második világháború idején jelentős kiképzőközpontként funkcionált. A Wehrmacht gyalogos és partraszálló egységeit és úttörőit a város környékén képezték ki. 1945. április 30-án a francia csapatok harc nélkül foglalták el a várost.

A háború befejeztével a lindaui kormányzati kerület a francia megszállási zóna része lett, és leválasztva az amerikai megszállású Bajorországról, különleges státuszt kapott. A következő tíz évben a terület hídként szolgált Németország és Ausztria franciák által megszállt területei között. 1955. szeptember 1-jén a várost visszacsatolták a Bajor Szabadállamhoz.

A világháború óta rendezik meg a városban a Nobel-díjasok Gyűlését (1955-ben itt született a mainaui nyilatkozat), és a lindaui Pszichoterápiás Hetet, ez utóbbit minden nyáron 4000 terapeuta keresi fel.