Em 1852, foi promovido a primeiro-tenente. Em 24 de dezembro de 1856, recebeu a patente de Capitão. Em dezembro de 1864, participou do cerco à Montevidéu, durante a intervenção militar brasileira contra o governo de Atanasio Aguirre no Uruguai. Pouco depois, o Uruguai, sob novo governo, mais o Brasil e a Argentina firmariam a Tríplice Aliança, contra a ofensiva do ditador paraguaio Francisco Solano López.

Em março de 1865, rumou com o Exército brasileiro para o Paraguai, que havia invadido a província de Mato Grosso. Deodoro comandava o segundo Batalhão de Voluntários da Pátria. Seu desempenho no combate lhe garantiu menção especial na ordem do dia 25 de agosto de 1865. No ano seguinte, recebeu comenda no grau de Cavaleiro da Ordem do Cruzeiro e, em 22 de agosto, a patente de Major.

Em 18 de janeiro de 1868 foi promovido a tenente-coronel, por atos de bravura. Também por atos de bravura, recebeu a patente de Coronel, em 11 de dezembro do mesmo ano. Pelo decreto de 14 de outubro de 1874, Deodoro foi promovido a brigadeiro, patente equivalente ao atual general-de-brigada. Em 1885, tornou-se pela segunda vez comandante d’armas da Provincia do Rio Grande do Sul, cargo exercido juntamente com o de vice-presidente da província. Tornar-se-ia, depois, presidente interino dessa mesma província. Em 30 de agosto de 1887, recebia a patente de marechal-de-campo.

Pelo seu envolvimento na “Questão Militar” – confronto das classes armadas com o governo civil do Império – Deodoro foi chamado de volta ao Rio de Janeiro. Na verdade, o Marechal Deodoro havia permitido que a oficialidade da guarnição de Porto Alegre se manifestasse politicamente, o que era proibido pelo governo imperial. Chegando ao Rio, Deodoro foi festivamente recebido por seus colegas e pelos alunos da Escola Militar. Foi, então, eleito primeiro presidente do Clube Militar, entidade que ajudara a constituir.

Em 1888 Deodoro foi nomeado para o comando militar do Mato Grosso. Permaneceu no posto somente até meados de 1889, quando voltou para o Rio de Janeiro.