La historia del edificio se remonta a la década de 1780, cuando las autoridades locales de Tallin —entonces conocida como Reval—, que formaba parte del antiguo Imperio ruso, impulsaron un proyecto para construir nuevos edificios administrativos. Originalmente, el edificio fue concebido como un palacio de justicia.^[1]​^[2]​

El conde Jakob Pontus Stenbock, un influyente aristócrata local y propietario de una gran finca en Hiiumaa, ganó la licitación para erigir el nuevo edificio en la colina de Toompea, en el centro de Tallin. El arquitecto encargado fue Johann Caspar Mohr, arquitecto provincial responsable del mantenimiento de los edificios públicos en Estonia y reconocido diseñador de casas señoriales locales.^[2]​

La construcción comenzó en 1787, pero casi de inmediato el gobierno imperial ruso se quedó sin fondos debido a los gastos derivados de la guerra ruso-turca (1787–1792). Como consecuencia, la provincia contrajo una deuda con Stenbock, y el edificio inacabado pasó a ser de su propiedad.^[1]​ Lo utilizó como residencia en Tallin, y hasta hoy el edificio conserva su nombre en su memoria. En 1828, tras la muerte de Stenbock, la propiedad fue pasando por varias manos hasta que en 1899 fue adquirida por la administración provincial y comenzó a utilizarse como palacio de justicia.^[3]​

Durante tanto el primer periodo de independencia de Estonia (1918–1940) como durante la ocupación soviética (1944–1991), el edificio siguió funcionando como tribunal. En las décadas de 1970 y 1980, su mantenimiento fue descuidado, lo que provocó el colapso de los techos de dos salas y del archivo judicial. Para 1991, cuando Estonia recuperó su independencia, el edificio estaba en riesgo de derrumbe. Fue completamente renovado entre 1996 y 2000, y al reabrirse ese año, se convirtió en la sede oficial del gobierno nacional estonio.^[1]​

El estilo arquitectónico del edificio corresponde a una forma bastante sencilla del neoclasicismo. La fachada principal está decorada con seis pilastras y dos semipilastras hechas de dolomita proveniente de Saaremaa, además de un frontón con molduras dentadas. Esta fachada da a un patio semicircular rodeado de dependencias auxiliares menos ornamentadas.^[4]​

La parte del edificio que da a la calle se caracteriza por la presencia de estas construcciones más discretas. En ese muro se encuentra una placa conmemorativa con los nombres de miembros del parlamento y del gobierno estonio que fueron asesinados por el régimen soviético estalinista. La vista más conocida del edificio es, sin embargo, su parte trasera, que al estar situada en el borde de la colina de Toompea, ofrece una vista despejada hacia el mar. En ese lado destaca un gran balcón sostenido por columnas dóricas.^[5]​^[1]​ En conjunto, el exterior del edificio conserva en gran medida su aspecto original. El interior, en cambio, sufrió graves daños durante la ocupación soviética y ha sido reconstruido en gran parte.^[6]​