Die K.Ö.St.V. Vandalia wurde am 2.4.1922 durch einen Beschluss unserer Mutterverbindung, der e.v. K.Ö.St.V. Frankonia Wien gegründet. Nach einer ersten stürmischen Zeit, berichten die Annalen von einem ersten Vandalen-Ball im Simmeringer Brauhaus im Jänner 1927. Mit der Selbstausschaltung des Parlaments im März 1933 gerät auch Vandalia in immer stärkere Turbulenzen aus denen sie sich erst 1957 wieder vollständig erholen wird. Seit Mai 1936 sind wir Mitglied im MKV.
Das 15. Stiftungsfest der Vandalia im April 1937 markiert den letzten schönen Moment in der Verbindungsgeschichte vor der kommenden dunklen Zeit. Im März 1938 erfolgt die Selbstauflösung der Aktivitas und die zwangsweise Auflösung des Alt-Herren-Vereins durch den Reichstreuhänder. In den kommenden Jahren der Auslöschung Österreichs, der Unterdrückung und Verfolgung, engagieren sich viele MKVer und Couleurstudenten im Widerstand. Doch auch in der dunkelsten Zeit brennt ein Licht. Mitten im Kriegswinter 1944 feiert unsere Vandalia im Geheimen ihre Weihnachtskneipe.
Nach den Kriegswirren erwacht das studentische Leben: Am 25. Mai 1946 wird unsere Mutterverbindung Frankonia reaktiviert, aber es dauert mehr als neun Jahre – nämlich bis zum 21. November 1956 – bis die Frankonia auch unsere Vandalia reaktivieret. Am 10. Jänner 1957, fast 19 Jahre nach der Selbstauflösung, wird die K.Ö.St.V. Vandalia mit einem Burschen-Convent im Restaurant „Zum guten Hirten“ in der Landstraßer Hauptstraße 55-57 reaktiviert. Die Verbindung wächst und gedeiht, bereits ein Jahr später findet die „Redoute in Blau“ in allen Sälen des Brauhauses statt, Tanzkurs mit Prof. Willy Fränzel inklusive. 1958 wird auch die erste Nachkriegs-Bude (Verbindungslokal) in der Gratian-Marx-Straße 7 eingeweiht. Es war dies die erste Bude in Wien mit einem Telefon. Damals noch Festnetz.
1961 kommt es zur Freundschaftsband-Verleihung mit unserer Mutterverbindung e.v. K.Ö.St.V. Frankonia.
1962 wird unsere aktuelle Verbindungs-Fahne durch unseren Bundesbruder HW KR P. Anton Stilling v. Ludwig geweiht.
Das Jahr 1972 markiert unser 50jähriges Bestehen, die Stiftungsfestmesse wird in der Pfarrkirche Neusimmering zelebriert, der Kommers findet im Palais Pallfy statt.
1977 gewinnen wir mit der e.v. K.Ö.St.V. Kreuzenstein Wien unserer zweite Freundschaftsverbindung dazu.
Es folgen Jahre der Blüte und des Wachstums, im Jahr 2000 wird unsere neue Bude in der Simmeringer Hauptstraße 128 bezogen. In dieser Zeit gedieh die Verbindung prächtig und hatte zuweilen pro Semester zwischen 20-25 Interessenten (Füchse). Heute steht Vandalia auf dem festen Fundament der ersten 100 Jahre unserer Geschichte und blickt frohen Mutes in die Zukunft.