1780-ban az akkor már Maria Theresiopolisba ellátogattak a német vándortársulatok is, a közönséget pedig a városi elöljáróság, valamint a hivatalukat itt betöltő tisztségviselők képezték. A későbbi években már számos magyar társulat is fellépett Szabadkán. 1818-ban a városi tanács úgy döntött, hogy a vándortársulatoknak „nincs helyük” tovább a gimnázium épületében, s erre a célra a Schultz-féle éttermet jelölték ki. A negyvenes évektől kezdve pedig a híres Fekete Sas nevű étteremben játszhattak az idelátogató színészek.
Közben a szabadkai sajtó egyre többet cikkezett arról, hogy „most már nélkülözhetetlen volna” egy állandó épület, „ahol Tháliának méltó helyet biztosítanának”, és egy állandó színtársulat létrehozását szorgalmazták.
Ezután, 1844-ben a szabadkai születésű Skultéty János építész engedélyért folyamodott a városhoz, hogy ellátogasson néhány helyre, ahol kisebb, de jól felszerelt színházi épületek vannak, amelyekhez hasonlót építhetnének Szabadkán is. A következő évben a Magisztrátus döntést hozott egy szálloda felépítéséről, ahol helyet kapna a színház is. A város vezetése elfogadta Skultéty tervét, és 1848 márciusában lerakták a szálloda- és színházépület alapkövét. Azonban a magyar forradalom és szabadságharc kitörése megzavarta a munkálatokat, amelyet csak 1853-ban tudtak folytatni. Ekkor épült fel a szállodaszárny, a következő évben pedig a színház építését is befejezték. A színház ünnepi megnyitóján, 1854. december 16-án Jósika Miklós Két Barcsay című előadását mutatták be.
A szabadkai színházi vezetőség 1855-ben szerződést írt alá Havi Mihállyal, amelyben havi tizennyolc előadás bemutatását vállalta. Közben Szabadkán egyre nagyobb érdeklődés mutatkozott az előadások iránt, és ennek köszönhetően 1870-ben megalakították a szabadkai Színügyi Egyesületet.
Molnár György, aki egy időben a színház művészeti vezetője volt, emlékiratában a következőket írta: „Szabadka egy csúnya nagy sárpocsolya”, de azonnal hozzátette, hogy a város központjában egy magas épület emelkedik ki a többi közül, az új színház, amelyben túlságosan kiemelt szerepű kávéházi szárny is helyet kapott. És valóban, abban az időben jóval kedveltebb és látogatottabb volt az épület kávéházi része, mint a színházi előadások.
A színházban minden helybéli úri családnak volt saját páholya, amelyre még az építkezés alatt tett szert. Azokat mindenki a saját ízlésének megfelelően és lehetőségeihez mérten rendezte be, aminek következtében a falakat is különböző színűre festették. A korabeli sajtó is ír arról, hogy „az így kialakult tarkaság nem nyújtotta a legkellemesebb összhatást”. Annak ellenére, hogy a páholyok örökösödés útján cseréltek gazdát, egy idő után a város költségén egységesen felújították őket, így helyreállt az épület belső összhangja. Bevezették a bérlethasználati díjat, amelyet akkor 20 forintban határoztak meg, és ezzel az összeggel is a színházat segítette, a városi költségvetés rendszeres évi támogatása mellett.
A Városi Tanács 1905-ben jóváhagyta az épület tatarozását, azonban a munkálatok folyamán az akkori Kossuth Lajos utca felőli külső fal megrepedt. A városban az a hír terjedt el, hogy a színház összeomlott. A későbbi évtizedekben a két társulatot is befogadó színházi épületen nem sok javítás történt. Állapota életveszélyessé vált, minek következtében a közelmúltban szinte teljesen lerombolták, s helyére újat kezdtek építeni. A tervek szerint 2012-ben fejezik be a monumentális, modern szabadkai színházi épületet.
