La primera iglesia de Salto fue una capilla muy pobre, atendida por el Cura Vicario de Paysandú o alguno de sus tenientes, dedicada a Nuestra Señora del Carmen. En 1831, siendo Vicario Apostólico del Uruguay D. Dámaso Antonio Larrañaga, recibió un oficio encabezado de esta manera: "los que suscriben, vecinos del pueblo de Salto, por sí y a nombre de todos los habitantes del distrito, suplican la erección de esta parroquia con el título de Nuestra Señora del Carmen".
El P. Larrañaga, el 2 de enero de 1832, emanaba este decreto: "Invocado el nombre de Nuestro Señor Jesucristo y de su Madre la Santísima Virgen María, y usando de la autoridad pontificia delegada con que nos hallamos, separamos y dividimos, y siendo necesario, desmembramos de la jurisdicción parroquial de Paysandú, la nueva Parroquia de Nuestra Señora del Carmen de Salto".
En 1852 se colocó la primera piedra de la nueva iglesia del Carmen, y a pesar de las contiendas civiles que sucedieron a la Guerra Grande, ya en 1855 pudieron los salteños inaugurar la iglesia en vísperas de Semana Santa, con una solemne procesión, en que las autoridades civiles, representando al Presidente de la República, asistieron corporativamente al acto, contribuyendo esto a dar inusitado realce a los festejos y cultos que se celebraron en esos días. En un periódico de Montevideo se publicaba la reseña de la procesión y demás ceremonias, describiendo el paso de la comitiva de esta manera: "Cerraba la procesión el Sr. Cura Párroco; a su derecha el Sr. Jefe Político, Sargento Mayor don Miguel Nieto, representando la persona de S.E. el Sr. Presidente de la República, Brigadier General D. Venancio Flores, nombrado especial padrino para este acto, llevando de ayudante al Comisario de Ordenes D. José Rivero. A su izquierda el escribano público D. Santiago D. Olivera, como notario de la Iglesia, rodeados de considerable número de vecinos respetables y el inmenso concurso que llenaba las tres cuadras que había de una a otra iglesia".
Para lo que era Salto en esos tiempos, la Parroquia del Carmen era un templo de extraordinarias proporciones y sus vecinos y feligreses estaban orgullosos con su Matriz nueva que llenaba una de las aspiraciones de sus fervores religiosos. Los detalles de ornamentación que faltaban se fueron terminando una vez inaugurado solemnemente el templo para celebrar los cultos con el esplendor debido.
En 1920, el obispo de Salto, Mons. Tomás G. Camacho, confió la Parroquia del Carmen a la Congregación Salesiana. El primer Párroco salesiano fue el P. Agustín Aschieri, que permaneció en ese cargo hasta su fallecimiento en 1961.
En 1955 el Arq. Horacio Terra Arocena recibió el encargo de reformar la iglesia, ampliándola con el actual presbiterio y dándole las líneas actuales, en sobrio estilo clásico.