Private Töchterschule (ab 1859)

Die Landarzttochter Euphrosine „Sina“ Kinkelin stellte 1858 an die Stadt Lindau einen Antrag zur Errichtung einer Töchterschule. Diesem wurde stattgegeben und 1859 begann der Betrieb einer privaten Erziehungs- und Unterrichtsanstalt im Bensperghaus in der Bindergasse auf der Lindauer Insel (heute Auktionshaus Zeller).

Städtische Oberschule (ab 1937)

1930 wurde die Schule in ein Lyzeum (Höhere Töchterschule) umgewandelt und 1937 erfolgte die Übernahme der Schule durch die Stadt Lindau als „Städtische Oberschule“. 1965 erfolgte die Umwandlung in ein Gymnasium mit neusprachlichem und sozialwissenschaftlichem Zweig und es kam zum Umzug in die Ludwig-Kick-Straße. 1971 wurde die Schule verstaatlicht; 16 Jahre später, im Jahr 1987, wurde erstmals in der Geschichte der Schule auch Jungen der Besuch ermöglicht. Da nun der bisherige offizielle Name Städtisches Gymnasium für Mädchen – Neusprachliches und sozialwissenschaftliches Gymnasium nicht mehr den neuen Begebenheiten entsprach, trug die Schule bis zur Umbenennung 1991 den Namen Gymnasium Lindau (B) II.

Valentin-Heider-Gymnasium (ab 1991)

1991 wurde der Name Valentin-Heider-Gymnasium verliehen.
Der Rechtsgelehrte und Ratsherr Valentin Heider (1605–1664) vertrat nach dem Dreißigjährigen Krieg als Gesandter auf dem Friedenskongress in Osnabrück die Rechte der Stadt und erreichte, dass Lindau Rechte und Freiheiten zurückerhielt, die es im Krieg verloren hatte. 1655 regte Valentin Heider an, sich um die nach dem Schrecken des Krieges verwahrloste Jugend zu kümmern, und begründete damit das Lindauer Kinderfest.

Eine neue Sporthalle wurde von Juni 2012 bis Juni 2013 errichtet und im Juli 2013 eingeweiht. 2017 wurde der Pausenhof des Valentin-Heider-Gymnasiums neu gestaltet und angelegt.