Para evitar la agravación de la situación tirante con el gobierno de Río de Janeiro, fue enviado el general Mitre como plenipotenciario a la capital brasileña.
Las instrucciones firmadas el 4 de junio de 1872 por Sarmiento y Tejedor se refieren a la amenaza de rompimiento del tratado de alianza a causa de la negociación separada del Brasil con el Paraguay.
"Una discusión directa de gobierno a gobierno, dicen las instrucciones, haciendo más tirantes las relaciones, podría dificultar un arreglo, igualmente conveniente y decoroso para ambos aliados, y es por esta razón que se ha resuelto encomendar al señor general Mitre la misión especial de entenderse sobre el particular con el gobierno del Brasil, a fin de arribar a un acuerdo que, ajustándose a las prescripciones del tratado de alianza y teniendo en cuenta los hechos que se han producido, restablezca la buena armonía que debe existir entre los dos gobiernos, así en el presente como en el futuro.
Las bases de ese arreglo podrían ser cambiadas con el barón de Cotegipe, y otras parecidas, a saber:
1º Reconocimiento explícito de parte del gobierno brasileño de la vigencia del tratado del 1º de mayo en todas sus estipulaciones de guerra como de paz.
2º Negociación separada de parte de la República Argentina con el Paraguay, con sujeción al referido tratado.
3º Desocupación de las fuerzas aliadas del territorio paraguayo, tres meses después de los tratados definitivos, según lo convenido en las conferencias de Buenos Aires.
4º Reconocimiento de la República de los tratados de Cotegipe en lo que no estuviesen en oposición con las bases anteriores".
Entre junio y noviembre de 1872 fue enviado por el presidente Sarmiento al Brasil, para negociar el apoyo de ese país a las exigencias argentinas sobre límites con el Paraguay para ello se entrevisto con el jefe de gabiente brasilero Silva Paranhos, vizconde de Rio Branco, al año siguiente representó a nuevamente al país en una misión en Asunción del Paraguay, durante la cual descubrió que el Brasil no apoyaba las reclamaciones argentinas, y apenas admitía que se fijara el límite sobre el río Pilcomayo.
Se le dan otras instrucciones para proceder en las discusiones y un margen amplio para cumplir su misión. Mitre llegó a Río de Janeiro el 6 de julio de 1872. En su discurso de recepción expresó:
"Que los objetivos especiales de su misión tenían por límite y por regla el mutuo decoro y la mutua conveniencia en el espíritu más amistoso y que para llenarlos se lisonjeaba de poder cantar con la cooperación y buena voluntad del ilustrado gobierno brasileño, y muy especialmente con la benevolencia de la majestad imperial, en cuya augusta persona saludaba respetuosamente la majestad de un pueblo libre".
Comenzó Mitre sus gestiones entrevistándose con el jefe del gabinete, Silva Paranhos, vizconde de Rio Branco. Se armó de paciencia, de ecuanimidad y de agudeza. y fue venciendo obstáculos hasta plantear los problemas en un terreno de cordialidad y de confianza mutuas y se convino en censurar enérgicamente la posibilidad de una guerra entre las dos naciones.
Fue una negociación laboriosa y el plenipotenciario argentino demostró tacto, habilidad, sutileza diplomática y firmeza cortés.
El resultado del esfuerzo años meses fue el restablecimiento de la cordialidad de relaciones entre la Argentina y el Brasil, con la firma de un convenio que puso fin a las divergencias suscitadas, en noviembre de 1872.
Al regresar a Buenos Aires, el ministro plenipotenciario fue objeto de demostraciones de adhesión a su persona y a su triunfo. Joaquín Nabuco, en su obra La guerra del Paraguay, escribió sobre la misión de Mitre:
"Desde el momento en que el gobierno argentino se hallaba en el fondo animado de un espíritu de concordia, disponiéndose, a pesar del estado de exaltación creado en la masa nacional por los partidos, a hacer concesiones al Paraguay, contentándose en último caso con la línea del Pilcomayo y aceptado el arbitraje en la cuestión de Villa Occidental (hoy Villa Hayes), no parecía haber motivo de serio disgusto. Por eso la agitación belicosa de principios de 1872 se aplicó, al conocerse la misión confiada al general Mitre en Río de Janeiro. Enviar a Mitre al Brasil con aquella embajada, era una hábil maniobra política, porque si fracasaba o si cediese demasiado a las exigencias del Imperio, quedaba inutilizado para la futura elección presidencial. Contribuyó Cotegipe a su nombramiento, diciendo a Tejedor que su propósito no había sido romper la Alianza; que el gobierno argentino podía hacer con las garantías que aquélla daba a las partes contratantes, lo que él mismo había hecho.
La primera dificultad estaba en las notas cambiadas de gobierno a gobierno. Mitre llegó a Río de Janeiro a primeros de julio de 1872 y empleó tres meses en resolverla, a causa de la escrupulosa minuciosidad con que Rio Branco, y puede decirse que el mismo emperador, ofendido por el lenguaje de la prensa porteña contra el Imperio, querían depurar las intencionadas alusiones de Tejedor.
Pero el 19 de noviembre, Mitre y el marques de San Vicente, plenipotenciario brasileño, firman el convenio restableciendo la Alianza, tal como se hallaba antes de los tratados de Cotegipe, dejando a éstos intactos y obligándose el Brasil a ayudar a su aliado en las negociaciones que a su vez iba a entablar. Contribuyó probablemente a la renovación del tratado el conocimiento que Rio Branco tenía de las ideas de Mitre, indicado igualmente para representar a la Argentina en las negociaciones de Asunción" ...