Mapa de Tacuarembó. Documento Planimétrico compilado por el Servicio Geográfico Militar a partir de fotoplanos | Fuente: Biblioteca Digital Trapalanda de la Biblioteca Nacional | Licencia: dominio público.
En esa fecha el presidente de la cámara de senadores, Carlos Anaya, que en esos momentos ejercía la presidencia de la República por hallarse ausente el presidente Manuel Oribe, promulgó la Ley N.º 158. Esta creaba los departamentos de Tacuarembó y Salto y establecía los nuevos límites del departamento de Paysandú. Pocos días después, el 14 de agosto, el gobierno nombró las nuevas autoridades, siendo designado como primer jefe político y de policía el señor Atanasio Lapido.
Los límites del nuevo departamento fueron provisorios hasta el 4 de julio de 1848 cuando se fijaron por una nueva ley.
Tacuarembó fue habitado desde la prehistoria por grupos de aborígenes. Su nombre deriva del idioma guaraní, posiblemente adjudicado por troperos misioneros que realizaban arreadas de ganado hacia las misiones jesuíticas. Un documento de 1702 menciona el río Tacuaremboty, que significa río de los cañaverales o tacuarales. Durante la época colonial, José Artigas repartió diversas suertes de estancia como parte de la política llevada adelante por los españoles para poblar la frontera.
Luego de la independencia, la zona norte de nuestro país, en virtud de la indefinición de la frontera con Brasil y la necesidad de poblarla, fue objeto de particular atención por parte del gobierno. En octubre de 1831 el presidente Fructuoso Rivera decretó la fundación de una villa en la zona de Tacuarembó. Esto se concretó el 27 de enero del año siguiente, cuando el coronel Bernabé Rivera fundó la villa de San Fructuoso, posteriormente ciudad de Tacuarembó. El lugar elegido fue el “Rincón de la Tía Ana”, en las costas del arroyo Tacuarembó Chico, donde ya existía un oratorio.
Entre el 22 y el 26, con la colaboración de un agrimensor, se realizó la mensura, deslinde y amanzanamiento del futuro pueblo y se adjudicaron chacras y solares a los primeros pobladores.
En 1837, cuando se creó el departamento, la villa contaba con más de 500 habitantes, juez de paz, cura párroco, y jefe militar. Para la administración de las zonas rurales se contaba con Tenientes Alcaldes, y para los asuntos urbanos una Comisión de Obras Públicas.
La nueva organización implicó a la formación de una Junta Económica Administrativa encargada de impulsar iniciativas que tendieran al desarrollo del departamento y que junto al Jefe Político, que también era jefe de policía, constituían las máximas autoridades departamentales.
En 1852 llegó a San Fructuoso el Presidente Juan F. Giro y permaneció seis días en San Fructuoso y durante su estadía hubo teatro, dos bailes y sortijas. Uno de los cronistas del diario de Montevideo que acompañaba la comitiva del presidente, sostenía que en la villa había 30 casas de material y 170 ranchos, 2 comercios mayoristas, 15 almacenes menor, una sola fonda (hotel), pero dos boticas (farmacias).
Durante el resto del siglo XIX diversos acontecimientos fueron jalonando la historia del departamento. Entre estos cabe destacar: la inauguración de la primera escuela en 1852, la construcción del edificio de la Jefatura de Policía en 1878, la creación del departamento de Rivera con territorios de Tacuarembó en 1884 y la inauguración del Teatro Escayola, el segundo del interior, en 1891.