A szabadkai önkormányzat 1890. december 24-én tűzte napirendre a gimnázium helyzetét. Ekkor szándékhatározatot hoztak új gimnáziumi épület emeléséről, valamint hozzávetőleges számítást is végeztek a költségekről. A várható költségek azonban riadalmat keltettek, az illetékesek igyekeztek kibúvót keresni a vállalt kötelezettségek alól. A következő év áprilisában indítványt terjesztettek a közgyűlés elé, hogy költségkímélés céljából valamely szerzetesrendnek adják át a gimnáziumot. Az indítványt el is fogadták.
Néhány nappal később a város küldöttsége már Pannonhalmára utazott, hogy tárgyaljon a Szt. Benedek-rend vezetőivel, azonban ajánlatuk nem talált pozitív visszhangra. A szerzetesrend meg is indokolta az elutasítás okát: a gimnázium átvételével rájuk hárulnának a beruházási költségek.
Az első kísérlet azonban nem szegi a szabadkaiak kedvét. A következő hónapokban sorra járják a tanító rendeket, de mindenütt elutasítják ajánlatukat. Egyedül a piarista rend mutatott hajlandóságot, de 1894 augusztusában velük is megszakadt a tárgyalássorozat. Közben a szegedi tankerületi főigazgatóság elrendeli, hogy a gimnázium köteles lesz az új épületet tornateremmel, rajzteremmel, kísérleti előadóteremmel és szolgalakással is kibővíteni.
A szerzetesrendekkel való sikertelen tárgyalások után a városi tanács határozatot hoz (1895. szeptember 25-én), hogy megtartja a gimnáziumot városi középiskolának, és bizottságot hozott létre azzal a feladattal, hogy javaslatot terjesszen a közgyűlés elé az új épület megépítésével kapcsolatban, valamint a „tanárok személyi ügyének rendezése érdekében”.
Közben a gimnázium ügye közügy lett. A sajtó rendszeresen foglalkozott a témával. A Szabadkai Hírlap például azt írja, hogy a bunyevác és a szerb tanácsnokok szerint a gimnázium elnemzetlenítő politikát folytat azzal, hogy ott szerzetes tanárokat kívántak alkalmazni. De arról is ír a korabeli sajtó, hogy a tanácsnokok egy csoportja azzal, hogy a világi tanárokat egyháziakkal akarja felcserélni, gyakorlatilag a tantestület ellen cselekszik, valamint a „hatalmasságok gyerekeinek” kedvez. A lap szerint a már működő tantestület egyforma szigorral jár el a diákok között, s ha kell, a „hatalmasságok” gyerekeit is megbuktatja.
A város által alapított bizottság 1896. június 30-án az önkormányzat elé terjeszti javaslatát. Eszerint az új gimnáziumi épület felépítésére a legmegfelelőbbnek a város központjában levő, Franke Lajosné és Pék Simon által tulajdonolt telek felelne meg. A közgyűlés a megvétel mellett dönt, s határoz arról is, hogy a tulajdonosok által kért 109 000 koronát többek között a tandíjak 10 koronáról 50 koronára való emelésével kívánja biztosítani.
Még az év júniusában pályázatot írnak ki az új, kétemeletes gimnáziumi épület tervrajzának elkészítésre, amelyre 15 pályamű érkezett. A közgyűlés pedig a helybéli Raichle Ferenc műépítészt bízta meg a részletes tervek és a beruházási költségek kidolgozásával.
A tervek elkészültével a legolcsóbb ajánlattevő vállalkozót, a helybéli Molczer Károlyt bízták meg az új objektum felépítésével. A munkálatokat Molczer 1898. június 6-án kezdte meg. Az építkezés a kedvező időjárási viszonyok miatt gyorsabban haladt az előirányzott tervekhez képest. Rendkívül enyhe tél köszöntött a városra 1898/99-ben, aminek következtében mind az ácsok, mind pedig a belső munkálatokat végző kőművesek zavartalanul dolgozhattak. Így a szerződésben kikötött időre elkészült a barokk stílusú új gimnáziumi épület. A telekből beépített rész 1856,3 m2-t foglalt el, az udvar területe pedig 3943 m2. A szabadkai Gimnázium épületéről dr. Horváth Mátyás a következőket írta: „Ha összevetjük a tantermek és laboratóriumok, szertárak arányát, azt kell mondanunk, hogy több mint egy évszázad múltán is irigylésre méltó, korszerű szellemet tükrözött az épület – az oktatási feltételeket illetően”.
A szabadkai középiskola 1899. augusztus 29-én tartotta első tantestületi ülését az új gimnáziumi épületben, s ezzel hivatalosan is megkezdte működését az új környezetben. Az új épület létrejöttével a későbbi évtizedek folyamán Szabadka a régió értelmiségi képzésének központjává vált.
