Im Jahre 1833 wurde eine private Töchterschule mit 26 Schülerinnen gegründet. Diese wurde im Jahre 1860 mit einer weiteren privaten Töchterschule vereinigt, die 1855 entstanden war. Nachdem eine dritte 1883 gegründete Töchterschule hinzukam, entstand 1890 die Städtische Höhere Mädchenschule, die 1912 als Lyzeum anerkannt wurde. 1928 wurde die Schule als Staatliches Oberlyzeum für Mädchen vom Preußischen Staat übernommen, 1939 erhielt sie den Namen Königin-Mathilde-Schule.
Seit 1955 ist die Schule ein Neusprachliches Gymnasium und Gymnasium für Frauenbildung. Als in Nordrhein-Westfalen 1974 die Kommunen die Träger der Gymnasien wurden, erhielt die Schule den Namen Königin-Mathilde-Gymnasium der Stadt Herford für Mädchen und Jungen. Seitdem gibt es die Koedukation.
Schulgebäude
Bei ihrer Gründung zog die Schule am 2. Mai 1833 zunächst in das Gebäude Ecke Neuer Markt/Komturstraße und von 1841 bis 1860 befand sich die Schule in der Brüderstraße 4. Anschließend erfolgten Umzüge zur Petersilienstraße 3 und in das Haus Unter den Linden 30 (heutige Hausnummer: 41). 1903 wurde das neue Gebäude an der Abteistraße bezogen, das später für den Neubau der Kreissparkasse Herford abgebrochen wurde. 1929 erfolgte der Umzug in das heutige Gebäude an der Vlothoer Straße, in dem sich von 1908 bis 1926 das Herforder Lehrerseminar befunden hatte.