A pedido de la provincia de Corrientes, a la que interesaba un camino que la vinculase al noroeste del país y a Bolivia, el gobierno nacional dispuso una expedición con ese fin.
Desde 1870, la expedición de Napoleón Uriburu, no se había hecho nada digno de mención en la frontera norte para conquistar los territorios en poder de los indios al norte del Salado y su prolongación desde Santiago del Estero a la costa del Paraná. La expedición de 1880 fue puesta al mando del mayor Luis Fontana y partió de Resistencia con destino a Salta, al revés de la de Uriburu, que había partido de Salta. La columna se formó con unos 60 hombres, de los cuales 29 eran zapadores armados, con 80 caballos, 20 mulas aparejadas y un carro con víveres secos y algunos bueyes para el consumo.
Partió el 4 de febrero y prolongó su marcha durante 103 días, dejando abierta una picada de 520 km que vinculaba Resistencia con Colonia Rivadavia, en el Bermejo Medio. El único encuentro con los indios ocurrió en La Cangallé, después Arias, 60 km al noroeste de la confluencia de los ríos Teuco y Bermejo, contra varias tribus coligadas.
Las armas de fuego de los expedicionarios y su disciplina vencieron a los indios, que dejaron 37 muertos, incluso el cacique principal, contra 4 muertos y algunos heridos de Fontana, entre ellos él mismo. Llegó a Fuerte Gorriti sin cabalgaduras; el 5 de agosto fue auxiliado por el jefe de la frontera de Salta y llegó así a Colonia Rivadavia.
Luis Fontana cumplió distintas tareas en expediciones de demarcación de límites explorando el Chaco Boreal, el Chaco Central y el Chaco Austral. Durante estos viajes de exploración del gran Chaco perdió su brazo izquierdo en un combate con los indígenas de la zona. En 1879 fundó la Ciudad de Formosa, y alcanzó el grado de teniente coronel.