Keski-Pohjanmaan Suojeluskuntajärjestön vuonna 1927 rakennuttama maakunnallinen keskustalo on yksi Suomen upeimmista, entisistä suojeluskuntataloista. Maakunnan suojeluskuntajärjestö tilasi v. 1926 talohanketta varten piirustukset Helsingistä arkkitehtitoimisto Frosterus & Gripenbergiltä. Saman arkkitehtitoimiston suunnittelemia ovat mm. Suojeluskunnan päämaja Helsingissä (Merikatu 5), Ilomantsin, Raahen ja Sortavalan suojeluskuntatalot.
Päätös Vartiolinnan rakentamisesta allekirjoitettiin 17.12.1926 ja työt käynnistyivät heti tammikuussa 1927. Peruskivi laskettiin Snellmanin päivänä 12.5.1927. Tilaisuudessa kivijalkaan upotettiin talon perustamiskirja. Rakennuksen piti valmistua jo samana vuonna, ja näin tapahtuikin, sillä kymmenvuotiaan Suomen itsenäisyyspäivää juhlittiin talon juhlasalissa 6.12.1927. Talo valmistui todella ennätysajassa – noin kymmenessä kuukaudessa.
Kolumäen itärinteeseen sijoittuva Kokkolan Vartiolinna muurattiin tiilestä kolmikerroksiseksi. Ensimmäiseen kerrokseen sijoittuivat aula, ravintola ja lämpiötiloja, toiseen kerrokseen rakennuksen päätila, suuri juhlasali. Siipiosassa sijaitsi piiresikunnan tiloja ja kellariin rakennettiin auto- ja tykkivajoja, varastoja sekä pistooliampumarata. Vartiolinnan tilat ja toteutus käsittivät kaikki juhlatalolle asetetut vaatimukset.
Rakennus edustaa 1920-luvun klassistista arkkitehtuuria puhtaimmillaan. Klassistisaiheiset koristeet toistuvat sekä sisä- että ulkotiloissa. Fasadin symmetristä keskiakselia korostavat neljä kolmen kerroksen korkuista tyyliteltyä korinttolaista pylvästä, joiden väliin sijoittuu keskimmäisen ikkunan ranskalainen parveke.
Kahden kerroksen korkuiset ikkunat ovat pyörökaariset ja lisäävät fasadien juhlavuutta. Ulkoseinissä on niukkailmeisiä medaljonkeja ja muita koristereliefejä. Seinäpinta on rapattu sileäksi ja maalattu ”Pompejin punaiseksi”. Katto on korkea aumakatto ja sitä kattaa lasittamaton tiili. Kellarikerros on rustikoitua betonia. Interiöörissä värivalintoja määrittivät mm. sotilaspukujen värit ja geometriset perusmuodot.
Vartiolinnasta tuli myös ensimmäinen julkinen rakennus Kokkolassa, johon asennettiin keskuslämmitys.
Jatkosodan rauhan yhteydessä, kun suojeluskunnat ja Lotta-yhdistykset lakkautettiin marraskuussa 1944, joutui niiden omaisuus valtion haltuun. Samana vuonna myös Vartiolinna siirtyi Suomen valtion omistukseen.
Vuonna 1947 Kokkolan kaupunki lunasti Vartiolinnan omakseen ja näin siitä tuli Kokkolan kaupungintalo.
Talossa tehtiin muutostöitä mm. vuosina 1938, 1970 ja 1974. Lopullinen saneeraus teatterin tarpeisiin ja alkuperäiseen asuunsa valmistui syksyllä 1999. Saneerauksen suunnittelivat kaupungin omat arkkitehdit Nils Erik Stenman ja Markku Peltoniemi.
Kesäkuussa 1999 Museovirasto teki Vartiolinnaa koskevan suojelumääräyksen.
Vuonna 2004 valmistui talon takapihalle, Vingenkadun puolelle, teatterin lavastamorakennus.
Tänä päivänä
Kokkolan kaupunginteatterin kotina toimivassa Vartiolinnassa on kaksi eri näyttämöä; 197 paikkainen päänäyttämö ja 58 paikkainen pieni näyttämö, Katariinan kamari. Sisääntuloaulassa toimiva Teatteriravintola Lumo tarjoaa puitteet sekä pienimuotoisille esityksille että kokouksille. Esitystoimintaa teatterissa on elokuun lopusta toukokuun loppuun.