1861 wird in der Weihburggasse (1. Wiener Gemeindebezirk) die private Lehr- und Erziehungsanstalt von der aus Deutschland stammenden Lehrerin Marie Hanke (später: Luithlen) mit sieben Schülerinnen gegründet und der Unterricht zu Beginn von ihr und einer befreundeten Lehrerin bestritten. Bald beteiligt sich auch Hankes späterer Mann Victor Luithlen am Unterricht und an der Leitung der Anstalt. Nach Victors und Maries Tod geht die Leitung 1893 an die Tochter Martha Luithlen über, die ebenfalls Lehrerin ist. Sie wird die administrative Leitung bis 1938 (Auflösung der Schule durch die Nationalsozialisten) innehaben.
1890 wird die Schule in ein Lyceum ("Privat-Mädchen-Lyceum Luithlen") umgewandelt, allerdings führt Martha Luithlen den 1900 normierten Lyzeallehrplan erst 1909/10 ein, wodurch die Schule das Öffentlichkeitsrecht erhält. Ab 1916/17 wird ein Reformrealgymnasium angegliedert. Ab 1922 wird die Schule als staatlich subventionierte Vereinsschule ("Mädchenmittelschule Luithlen") geführt.