Hasta antes de 1859, en el mismo lugar donde se construiría el palacio municipal existió una casa muy grande de madera y paja. En ella se llevaban a cabo los trabajos administrativos y también las actividades militares de quienes prestaban sus servicios en Tizimín. El espacio donde se encontraban estas oficinas comenzaba en la calle 50 y terminaba donde iniciaba la casa de los Mezo.
El antiguo palacio se construyó en el mismo sitio donde se encontraban las oficinas mencionadas. En esos años se comenzó a edificar el nuevo palacio de estilo lombardo, cuyas columnas de piedra labrada contaban con capitel y basamento sencillos. Los arcos que las unían eran de medio punto y entre uno y otro había una distancia de cinco metros; en total, se construyeron veinte arcos.
La construcción debió comenzar después de los asesinatos de los mayas de X-Maben en 1853 y concluyó en 1882. Los tres arcos centrales fueron modificados en 1927, cuando en su lugar se levantó la torre del reloj, hecha de cemento armado. El arco central era más ancho que los demás de la arquería, y a los lados las paredes formaban dos arcos cuadrados hasta ocupar el espacio. Sobre este sitio se construyó una torre de más de 15 metros de altura, considerada una obra muy bella y bien proporcionada. En ella se instaló un reloj de una sola carátula orientada hacia el sur de la población; años después se le añadieron dos carátulas más, una al este y otra al oeste.
Toda la construcción del palacio estaba distribuida de la siguiente manera: de oeste a este, comenzando por el lado oeste, se encontraba el departamento de policía y, detrás, la cárcel municipal, la cual estaba dividida en cinco áreas. Estas eran nombradas por la gente y las autoridades como cárcel número 1, 2, 3 y 4, mientras que la celda número 5 se destinaba a los presos por delitos más violentos. En la actualidad, estas celdas aún se conservan, pero han sido adaptadas como pequeñas oficinas pertenecientes al departamento de agua potable y servicios públicos municipales. El patio trasero, que colindaba con la escuela Otilia López, tenía más de un metro de profundidad. Allí siempre había una escalera de madera que servía para subir e izar la bandera en la parte más alta de la torre. Al frente de esta existían una puerta y un balcón, desde donde cada 15 de septiembre se ondeaba la bandera nacional.
También se utilizaba otra escalera para que el encargado pudiera dar mantenimiento al reloj municipal. En la parte oriente de la torre, sobre el techo del palacio, se construyó un pequeño espacio donde se colocó una campana que sonaba cada hora exacta. El técnico que dio mantenimiento al reloj durante más de 60 años fue don Hernán Domínguez Zermeño, un personaje muy estimado que llegó de la ciudad de Progreso y fue conocido en Tizimín como “el relojero Domínguez”.