El 31 de marzo de 1906, el gobernador del estado Ing. Olegario Molina Solis daba por concluida la obra del Paseo de Montejo.
Aunque fue en 1906 que se inauguro oficialmente, la idea del Paseo de Montejo se remonta a 1888 cuando el señor Rafael R. Quintero presento ante las autoridades del gobierno del General Guillermo Palomino la propuesta de promover un nuevo paseo en la ciudad. La primera piedra fue colocada el 5 de febrero de 1888, coincidiendo con el aniversario de la promulgación de la constitución. El paseo llevaría por nombre ‘De Montejo el adelantado’.
Aquel año se creó la comisión del paseo, la cual se encargaría de comprar terrenos y de hacer planos y las primeras gestiones para propocionarle a merida una avenida digna de los tiempos que corrían en la península.
Por entonces el estado de Yucatan era el segundo estado en crecimiento económico y cultural, la primera ligada a Estados Unidos y la segunda a Francia. El esplendor economico, aprovechado por los dueños de las haciendas henequeneras propició la creación del Paseo de Montejo el Adelantado. Pese al entusiasmo inicial, la obra fue abandonada ese mismo año y su construcción se reanudo hasta 1898 durante el gobierno del general Francisco Canton.
En la época en la que gobernó Yucatán Salvador Alvarado, se pretendió extender el Paseo hacia el sur, esta idea continuó en la cabeza de las autoridades de los años cuarenta y en los sesenta finalmente pudieron adquirir el terreno al sur del Paseo para iniciar lo que sería la avenida Manuel Cepeda Peraza pero solo pudieron adquirir este predio, pese a que la idea original pretendía extender la vía hasta el parque Eulogio Rosado. Este espacio al inicio del Paseo permanecería como un lunar en el paseo, hasta 1995 cuando se reconstruyó con el nombre de “Remate de Paseo de Montejo.
En el año 1938, el ingeniero Humberto Canto Echeverría mandó cambiar su nombre por el de Paseo de Nachi Cocom, aunque nadie, hasta la presente fecha, lo llama de este modo.
Nuestro Paseo se encuentra ornamentado con varios monumentos; en 1906 se instaló el Monumento a Justo Sierra O’Reilly en lo que entonces era el final del Paseo, en enero de 1926 se concluyó el obelisco en memoria del gobernador Felipe Carrillo Puerto. Entre 1945 y 1956, el escultor Rómulo Rozo esculpió el Monumento a la Patria en la glorieta al norte del Paseo. En cuestión de monumentos, la última adición que tuvo el Paseo fue la colocación en 2010 de la estatua de Francisco de Montejo el Adelantado, al lado de su hijo del mismo nombre, apodado «El Mozo», fundador de la ciudad de Mérida.
El Paseo de Montejo ha tenido tres prolongaciones hacia el norte, a lo largo de su existencia. La primera traza partía de la calle 47 hacia el norte, terminando en la glorieta en que se erigió el monumento a don Justo Sierra en 1906, lo que equivalía longitud de 1,280 metros lineales. En el año 1925, el entonces Gobernador, doctor Álvaro Torre Díaz, lo hizo prolongar siempre hacia el norte, en un tramo de 440 metros lineales, para lo cual tuvo que comprar parte del terreno que comprendía la Escuela Modelo, esto extendió el paseo hasta la glorieta donde hoy se encuentra el Monumento a la Patria. Durante la gestión de Canto Echeverría, se construyó una amplia desviación hasta el Campo Deportivo Salvador Alvarado. El tercer tramo de su prolongación, comunica la glorieta del Monumento a la Patria con la Colonia México, siempre al norte de la ciudad, en una extensión de 1, 200 metros lineales.
El paseo de Montejo presenta la incongruencia del tamaño de los predios, explicado por Leopoldo Tomassi así:
«Los ingenieros que se encargaron de proyectar y de trazar nuestro principal Paseo, a fines del siglo pasado, cometieron el gravísimo e irreparable error de construirlo en medio de una serie de manzanas existentes, en vez de prolongarlos sobre el eje de la calle 58, con la misma anchura que entonces se deseaba. Tal como se construyó quedaron a sus lados dos filas angostísimas de manzanas, de unos 30 a 35 metros de fondo, insuficientes para el tipo de residencias a que se destinaban. En esa época ya estaban abiertas las calles 56 y 58, y los propietarios de predios habían adquirido ya legítimos derechos para ocupar los frentes de cada una de esas calles. Si se hubiera aprovechado el eje de una de ellas (aún dándole al Paseo los 42 metros de ancho que actualmente tiene) hubieran quedado a sus lado manzanas más útiles, de unos ochenta metros de fondo, lo suficiente para dejar la mayor superficie sobre el Paseo y pequeños predios sobre las mencionadas calles 56 y 58. El resultado desfavorable se observó después, cuando se construyeron las primeras residencias sobre el Paseo de Montejo. Con el ancho actual de sus manzanas colindantes las casas parecen como «encajonadas», sin patios ni jardines suficientes y proporcionados a la importancia del Paseo»
Otros arquitectos contemporáneos han mencionado que este «error» es premeditado, pues se buscaba que sólo quienes tuvieran residencias sobre el Paseo, accedieran a el.
Pese a que continua siendo la avenida de excelencia de la ciudad de Mérida, ha tenido varios agravios en su fisionomía debido al desarrollo comercial, el cual le arrebato algunas de sus casonas más importantes para convertirles en edificios comerciales, esto ocurrió principalmente en la década de los cincuenta, sesenta y setenta. A partir de entonces comenzó a cuidarse la fisionomía del Paseo, en 1979 se instaló el ya característico ladrillo rojo en las aceras.
