Szkoła została utworzona 1 marca 1991 r. na mocy zarządzenia kuratora oświaty i wychowania w Elblągu wydanego niespełna miesiąc wcześniej. Początkowo działała jako jednostka budżetowa kuratorium.
Pierwszą siedzibę II LO miało w budynku byłego Domu Dziecka „Przyjaźń” przy ul. 500-lecia 98. Pierwszym dyrektorem został Jan Pawlina (pełnił tę funkcję przez dwie dekady), który pierwszych uczniów powitał podczas rozpoczęcia roku szkolnego 2 września 1991 r.
22 marca 1991 r. o powstaniu nowego liceum napisały „Nowiny Malborka”. Gazeta zamieściła obszerny tekst autorstwa Jana Pawliny. Przytaczamy jego fragmenty:
Na gruncie wielkich przemian istnieje ogromna potrzeba wychowania człowieka o nowej mentalności i spojrzeniu na otaczającą go rzeczywistość. Aby sprostać temu, należy realizować nowe założenia wychowawcze, wyrażające się w takich wartościach jak: zdolność do samodzielnego myślenia, prawość w postępowaniu, rozbudzanie uczuć społecznych i patriotycznych, tolerancja religijna i wyznaniowa, pracowitość. Dążyć należy, aby ostatecznym celem było wychowanie obywateli zdolnych do przetwarzania polskiej rzeczywistości, do wydźwignięcia narodu z niezwykle ciężkiej sytuacji społecznej, moralnej i materialnej. Takie cele wychowawcze przyświecają II Liceum Ogólnokształcącemu. Wokół organizacji tej szkoły urosło wiele mitów i niedomówień. Jako organizator II LO zapewniam, że będzie to szkoła dla każdego młodego człowieka, któremu drogie są ideały wolności myślenia, słowa, twórczej pracy i samorządnego działania. Myślimy również o nowatorskich rozwiązaniach dydaktycznych. Pragniemy, aby szkoła ta przysposabiała młodzież do śmiałych poczynań i dużych dokonań. Niech szkoła ta stanie się darem miasta dla tych, którzy czują się pokrzywdzeni, i dla tych, których ogarnia radość. Niech weźmie górę realizm, w zapomnienie pójdzie niechęć i niezadowolenie. Stańmy razem do wspólnego działania, mając na uwadze mądrość Aleksandra Kamińskiego: „Mądrość ich zasadza się na tym, że są uczniami”. Dajmy szansę zrealizować te słowa młodemu pokoleniu Malborka.
W początkowym okresie szkoła prowadziła nauczanie w klasach o profilach: matematyczno-fizyczny, podstawowy z rozszerzonym programem nauczania języka zachodniego, humanistyczny z rozszerzonym programem języka zachodniego.