El sitio que ahora ocupa el Carmen Alto fue uno de los primeros que los conquistadores llegados a Oaxaca con Alvarado y Cortés escogieron para establecer el culto cristiano. Ya a mediados del siglo XVI había ahí una ermita consagrada a la Santa Veracruz.
Diferentes fuentes citan los años 1669, 1679 o 1699 como fechas en que la comunidad oaxaqueña de carmelitas descalzos recibió del obispado la cesión de la ermita de la Santa Cruz y, del ayuntamiento, la donación del terreno. El templo del Carmen no se finalizó antes del año 1751, manteniéndose prácticamente inalterado hasta la actualidad.
Después de la secularización de las propiedades de la Iglesia, se produjo la prohibición de fundar o erigir nuevos conventos y demás. Los pocos carmelitas que aún quedaban en la casa abandonaron Oaxaca. El templo quedó clausurado durante varios años. En 1889 lo adquirió el obispo monseñor Eulogio Guillermo Guillow y se reconstruyó para que sirviera como residencia episcopal. Gran parte del claustro fue adoptado como colegio-seminario. En 1925, todo el conjunto pasó a ser propiedad federal.
El balance compositivo responde al juego de luz y sombra provocado por su estructura y los espacios arquitectónicos, así como a la delicadeza de las obras incorporadas a la fachada.
Dos entradas atriales idénticas, una al poniente y la otra al sur, cuentan con un vano central de medio punto flanqueado por pilastras y rematado por una hornacina; en sus partes macizas se empleó cantera.
La disposición general del templo es de cruz latina, en cuyo brazo sur se prolonga la capilla anexa. Comienza con el pórtico o nártex, sobre el que se levanta su portada principal. Consta de tres bóvedas de aristas que reposan en arcos de medio punto.
La portada principal la forma todo lo que es la fachada y se compone de tres cuerpos. El primer cuerpo corresponde al nártex; está fabricado en piedra amarilla y se compone de tres arcos de medio punto que arrancan de robustos pilares. Los arcos están separados por tres medias muestras toscanas que rematan en un entablamento que da origen al segundo cuerpo. Este está fabricado en cantera amarilla y se compone, al centro, por un relieve de forma cuadrada que corresponde a la Virgen del Carmen; en los costados tenemos un par de medallones, también en relieve, con motivos simbólicos de la orden. Este cuerpo remata en otro entablamento, donde se origina el tercer cuerpo, fabricado también en piedra amarilla. En esta zona tenemos, al centro, la ventana que ilumina al coro, flanqueada por dos medias muestras con capiteles con detalles corintios y, para terminar, en los extremos, dos remates en relieve en forma de flama.
La portada lateral se forma de tres cuerpos. En el primero tenemos un vano con arco de medio punto de la puerta de acceso, decorado por canaladuras en el arco y las jambas. En cada uno de los costados tenemos pares de columnas de fuste decorado con rombos y flores, con capitel de estilo corintio, que remata en un entablamento que une los dos pares de columnas, de donde nace el segundo cuerpo, formado por un nicho que aloja una escultura labrada en piedra que corresponde a San José y el Niño, flanqueada por pilastras de fuste decorado que rematan en un pequeño cornisamento. En los extremos de este cuerpo se localizan dos plintos con rombos en bajorrelieve y pináculos.
El tercer cuerpo lo forman una cruz tallada en alto relieve en forma de cordón y enmarcada con relieves moldurados siguiendo la forma de la cruz.
El primer tramo de la nave lo ocupa el sotocoro. Sus dos segmentos de bóveda rebajada de cañón corrido con lunetos reposan en arcos, los cuales se apoyan en impostas.
En el crucero, el espacio se eleva gracias al tambor octagonal apoyado en pechinas, sobre el que se alza una cúpula gallonada.
Tanto el ábside como los brazos del crucero llevan bóvedas semicilíndricas de cañón corrido. La capilla de Santa Teresita es una nave corta de dos tramos: el primero, abovedado con cañón y lunetos, y el segundo, cubierto por cúpula de planta octagonal.
En el siglo pasado se colocó en la nave un pavimento con figuras de mosaico de buena calidad y, recientemente, un piso de ónix en el presbiterio.
