Po ilgos kovos už lietuvių kalbos lygiateisiškumą 1922 m. balandžio 20 d. įsteigta pirmoji lietuvių gimnazija Klaipėdoje.
Gimnazijai vadovavo dr. V. Gaigalaitis, M. Krukis, P. Mašiotas, dr. K. Trukanas, E. Ingaunis, V. Plečkaitis, J. Slavėnas, J. Balakauskas, J. Banaitis, V. Stalionis, R. Šulskis, E. Prižgintas, R. Bloškys. Šiuo metu gimnazijos direktorius – S. Ruiba.
Svarbiausi gimnazijos istorijos momentai:
- 1930 m. gimnazijai suteiktas Vytauto Didžiojo vardas.
- 1934 m. pastatyti gimnazijos rūmai.
- II pasaulinio karo metais gimnazija buvo evakuota į Palangą.
- 1955–1996 m. K. Donelaičio vidurinė mokykla.
- 1972 m. mokyklos pirmo aukšto vestibiulyje atidengtas K. Donelaičio biustas (skulpt. P. Deltuva), įkurti K. Donelaičio, gimnazijos bei gamtos apsaugos muziejai.
- 1982 m. restauruota ir vitražais papuošta iškilmių salė (arch. N. Piekautienė, vitražų aut. H. Kulšys).
- 1991 m. ant mokyklos fasado atstatyti Gedimino stulpai bei užrašas: „Ir šviesa, ir tiesa mūs žingsnius telydi”.
- 1995 m. mokyklai suteiktas gimnazijos statusas.
- 1996 m. gimnazijai grąžintas Vytauto Didžiojo vardas.
- 1999 m. gimnazijos antrojo aukšto vestibiulyje atidengtas skulptoriaus V. Grybo sukurtas Vytauto Didžiojo biustas.
- 2012 m. balandžio 20 d. atidengtas gimnazijos statytojo, direktoriaus Kazio Trukano bareljefas (autorius Adomas Skiezgelas).
- Gimnaziją aukso medaliais baigė 18, sidabro – 38, su pagyrimu – 267 mokinių.