Nachdem die Herzogtümer Schleswig, Holstein und später Lauenburg preußische Provinz geworden waren, wurde die Stadt Schleswig durch allerhöchsten Erlass vom 20. Juni 1868 zum Sitz des Oberpräsidenten und des Regierungspräsidenten bestimmt. Der Unterbringung dienten anfangs Provisorien, Räume im Schloß Gottorf und im Prinzenpalais (Schleswig-Holsteinisches Landesarchiv, Abteilung 309, Nummern 23667, 23660, 23716, 23813, 23739, 23680, 23848, 23670, 23817, in chronologischer Reihenfolge).
Die Forderungen zum Bau eines eigenen, repräsentativen Regierungsgebäudes wurden immer stärker. Vom Planungsbeginn an stand das Vorhaben unter Termindruck. Am 23. April 1875 wurde die Königliche Regierung in Schleswig vom Finanzminister, dem Minister des Innern und der Obersten Technischen Instanz der Preußischen Staatsbauverwaltung, dem Minister für Handel, Gewerbe und öffentliche Arbeiten angewiesen, "ungesäumt" die Vorbereitung zum Neubau des Dienstgebäudes zu treffen, "damit derselbe sofort beginnen kann, sobald seine Majestät der Kaiser und König, dazu die nachgesuchte Allerhöchste Genehmigung erteilt haben wird."
Die Genehmigung des Kaisers ließ nicht lange auf sich warten. Schon sieben Tage später, am 30. April 1875, genehmigte Wilhelm I. das Bauvorhaben nach Maßgabe der Kostenanschläge, Situations- und Bauzeichnungen. "Die Kosten sind"
, heißt es in der Genehmigung weiter, "soweit sie nicht bereits disponible! gestellt sind, nach Bedürfnis auf den Extraordinarienetat der Bauverwaltung auszubringen."
Neben anderen großen staatlichen Bauvorhaben war der Neubau des Regierungsgebäudes in Schleswig aus den Frankreich auferlegten Reparationszahlungen finanziert worden, in der Folge des deutschfranzösischen Krieges 1870/71.
Entwurf und Bauleitung oblagen der Preußischen Bauverwaltung, der Amtsvorgängerin der heutigen Landesbauverwaltung Schleswig-Holstein. Der Entwurf war dem Königlich-Preußischen Landbaumeister. Die Dienstbezeichnung "Landbaumeister" folgte einer überkommenen Regelung in den Ortsinstanzen der früheren altpreußischen Provinzen (bevor Schleswig-Holstein preußisch wurde). Heinrich Koehler übertragen worden. Koehler entwarf eine 93,00 Meter lange, viergeschossige Dreiflügelanlage mit Mittel- und Eckrisaliten. Die Nordwestecke des Gebäudes nimmt einen Teil der Grundfläche des abgebrannten Palais des Grafen von der Naht (Dernahtsches Palais), des später nach Besitzerwechsel benannten Bielkelschen Palais in Anspruch. (Die Hoffnung der Schleswiger, dass das Bielkesche Palais wieder aufgebaut würde, hatte sich nicht erfüllt.)
Die Pläne und die dazugehörigen Erläuterungsberichte für das neue Regierungsgebäude waren im März 1874 vorgelegt worden. Die Bauunterlagen wurden von der Mittelinstanz, der Königlichen Regierung in Schleswig und der Obersten Technischen Instanz in Berlin "revidiert". Auch in der heutigen Landesbauverwaltung besteht die Dreigliedrigkeit dieses Verfahrensweges.
Die Verwirklichung des Entwurfs veränderte damals das Stadtbild entscheidend. Die gewaltige, blockhafte Baumasse des Gebäudes trat hervor. Ganz offensichtlich sollte das neue Bauwerk den preußischen Machtanspruch gegenüber der - inzwischen zur Kaserne gewordenen - ehemaligen herzoglichen Residenz Schloss Gottorf deutlich machen. Bemerkenswert ist, daß sich Geschosszahl und Geschosshöhen des Regierungsgebäudes dem Schloß Gottorf angleichen, sogar das erste Obergeschoß, das Mezzanin, ist, wie beim Schloß, deutlich niedriger als die übrigen Geschosse. Aber auch in seiner ganzen Haltung, in seiner äußeren und inneren Durchbildung und in der Wahl der Materialien setzt der Bau andere als gewohnte, hergebrachte Maßstäbe. Die in den Formen des sogenannten Rundbogenstils konzipierte Anlage mit starken horizontalen Gliederungen weisen auf Stilelemente der italienischen Backsteinrenaissance hin. Teilweise fremdartige, sicher nicht von Schleswig-Holstein ausgehende Einwirkungen bestimmen in weiten Teilen die Haltung des Hauses. Es liegt daher nahe, daß von leitenden preußischen Baubeamten "höheren Orts" Steuerung und Einflussnahme auf das Entwurfsgeschehen ausgegangen sind.
Bei der äußeren Gestaltung herrschen glatte, gelb-rötlich braune Verblender vor, im Grunde keine Besonderheit, Gliederungsmerkmale wie Granit, Sandstein und gelbe Terrakotten dagegen unterstreichen die von der heimischen Bauweise abweichende Materialwahl. Wappenschmuck in den Friesen, im Mittelrisalit die Wappen der Herzogtümer Schleswig, Holstein und Lauenburg, ergänzen die reiche Gliederung. Selbst die Dacheindeckung mit englischem Schiefer in Rechteckdeckung (englische Deckung) ist nicht gerade bindend für Schleswig.
Über dem Hauptgesims befanden sich, jeweils im Bereich der Risalite, Attiken mit aufgesetzten Akroterien aus Sandstein, Adler und Wappen darstellend.
Dem Äußeren des Gebäudes entsprechend ist auch das Innere gestaltet: Säulenstellungen, Pilaster, Architrave, Friese und Stukkaturen im überreichen Ausmaß, gußeiserne Treppen und zahlreiche Malereien bestimmen auch die innere Haltung des Bauwerks.
Nach Fertigstellung des Gebäudes nahm die Oberste Technische Instanz, die den Entwurf "revidiert" hatte, in einer kritischen Betrachtung, die die bekannten preußischen Grundsätze der Strenge und Sparsamkeit anklingen lässt, Stellung:
"Das Gebäude gewährt in seiner äußeren Erscheinung den Eindruck eines durchaus soliden und mit tadellosen Materialien hergestellten Bauwerks, dessen architektonische Detailformen in dem …
Die Veranlassung zum Bau und Entwurf