Die erste erhaltene urkundliche Erwähnung der Mainau stammt aus der ersten Hälfte des 13. Jahrhunderts. Damals gehörte die Insel zum Kloster Reichenau. Um 1265 ließen sich die ersten Ritter des Deutschen Ordens, der während des dritten Kreuzzugs gegründet worden ist, am Bodensee nieder. Zunächst hatten sie ihren Sitz auf Burg Sandegg im Thurgau, ab 1271 dann auf der Mainau. Im Laufe der Zeit kamen weitere Ländereien am Südufer des Überlinger Sees in den Besitz des Ordens und die Kommende (Niederlassung) Mainau wurde zu einer der größten und mächtigsten in der Ballei (Verwaltungsbezirk) Elsaß-Burgund.
Im Dreißigjährigen Krieg eroberten 1647 schwedische Truppen die Insel. Sie blieben dort bis 1649 und sollen die Insel verwüstet und bei ihrem Abzug völlig ausgeplündert haben. Nur die bronzene Kreuzigungsgruppe, das Schwedenkreuz, das ihr heute noch sehen könnt, wenn ihr von der Landseite auf die Mainau kommt, mussten sie zurücklassen. Warum? Davon erzählt eine Sage: