Es construida sobre el terreno que había ocupado el primer mercado público de la ciudad, conocido genéricamente como “Mercado Central” que con diferentes nombres, según la época y el gobernante, existió allí entre 1850 y 1975.
Cuenta la tradición que cuando se regresan los poderes provinciales de Tacotalpa a San Juan, en el año de 1795, se buscó organizar una zona para la compraventa de lo que necesitaba la población para subsistir, por lo que se decidieron por una parte de El Playón del río Grijalva, justo donde acaba El Barranco, más o menos donde hoy se encuentra el cine Sheba y Banamex.

Por ello fue lógico que hacia 1850, pensando en dar orden, limpieza y galanura a la ciudad, se construyera un nuevo mercado en la misma zona, con fácil acceso desde el río (hoy la calle Rafael Martínez de Escobar) y no tan inundable como lo era el resto de la zona, El primer paso fue un decreto del gobernador para hacerlo, pero fue hasta 1854 que el Ayuntamiento del Centro le compró un terreno a la señora Claudia Andrade de Rovirosa (madre del Sabio Rovirosa), el otro fue donado por ella, para tal fin y con la condición de que una vez que se cambiara su uso fuera devuelto a su descendencia, cosa que nunca se dio. Las cosas seguían caminando pero muy lentamente por lo que es hasta el 16 de septiembre de 1859 en que es inaugurado por el gobernador, don Victorio Victorino Dueñas Outrani.
Este mercado fue el primero que tuvo la ciudad y el único hasta el año de 1906, en que se inaugura el Mercado Público General Porfirio Díaz, en el espacio que hoy ocupa el Centro Cultural Villahermosa, frente al Parque Benito Juárez. Por esta razón es que la actividad económica, política y social de la ciudad se artículo en torno a esta zona: los muelles de pasajeros y de carga, este último en línea con la calle 27 de Febrero de 1864 (hoy Rafael Martinez de Escobar) para facilitar el acceso de las mercancías al mercado; la primer zona hotelera de la ciudad (Arcos, Gran Hotel Palacio, la Casa de Los Azulejos, el San Diego y el María Dolores, entre otros); el Palacio de Gobierno a partir de 1894; la cárcel pública, hasta 1944; el Museo de Tabasco de noviembre de 1952 a 1979; El Xóchitl, Singer, farmacias Marina y La Mejor, Glender’s, Me lo Llevo, Quintero, Pineda Hermanos, más diversos cafés, restaurantes, abarrotes, bodegas, almacenes, zapaterías y tiendas diversas.

En 1975 el mercado fue demolido y trasladado a su ubicación actual con el nombre oficial de Mercado Público Coronel Gregorio Méndez Magaña, aunque por todos conocido como el Mercado de La Sierra ya que se ubicó en la última loma urbana del camino a la región de La Sierra. Por lo que en el espacio que dejó libre fue construido e inaugurado el 20 de noviembre de 1976, un parque público que hizo honor al defensor de San Juan Bautista durante la Intervención norteamericana, el comerciante Juan Bautista Traconis. Pero el nombre y la fisonomía del parque público no duraron mucho ya que fue reestructurado y rebautizado a fines de 1982.
Con la representación del presidente de la República Lic. Miguel de la Madrid Hurtado, el Lic. Mario Ramón Beteta, Director General de PEMEX, el gobernador del Estad, Ing. Leandro Rovirosa Wade y el oficial mayor del gobierno de Querétaro, develaron la placa alusiva al parque y fuente dedicado a la Corregidora de Querétaro, doña Josefa Ortíz de Domínguez. Esto sucedió el 13 de diciembre de 1982 a las 20:00 horas. En dicha ceremonia le correspondió al Lic. Pascual Bellizia Castañeda, presidente municipal de Centro, agradecer al Gobernador del Estado de Querétaro por la donación que hizo de la estatua, réplica de la existente en aquel estado.
A lo largo de su existencia este espacio público ha tenido dos usos y diversos nombres:
- Mercado Central, de 1859 a 1925;
- Mercado público Lic. Tomás Garrido Canabal, del 22 de noviembre de 1925 a enero de 1937;
- Mercado público Coronel Gregorio Méndez Magaña, del 6 de enero de 1937, aunque en 1975 fue trasladado a su ubicación actual;
- Parque público Juan Bautista Traconis, del 20 de noviembre de 1976 a diciembre de 1982;
- Plazuela de La Corregidora, desde el 13 de diciembre de 1982.